1

When we talk about Θ(g) are we referring to the highest order term of g(n) or are we referring to g(n) exactly as it is?

For example if f(n) = n3. And g(n)=1000n3+n does Θ(g) mean Θ(1000n3+n) or Θ(n3)?

In this scenario can we say that f(n) is Θ(g)?

JungleJeem
  • 51
  • 8
  • Possible duplicate of [What is a plain English explanation of "Big O" notation?](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – Dima Chubarov Aug 30 '16 at 06:08
  • @DmitriChubarov I believe Theta and Big O represent very different aspects of the complexity of an algorithm. – JungleJeem Sep 01 '16 at 03:07
  • One answer in particular details the relations between three kinds of notations for complexity classes http://stackoverflow.com/a/6620071/1328439 – Dima Chubarov Sep 01 '16 at 14:21

2 Answers2

1

Θ(g) yields sets of functions that are all of the same complexity class. Θ(1000n3+n) is equal to Θ(n3) because both of these result in the same set.

For simplicity's sake one will usually drop the non-significant terms and multiplicative constants. The lower order additive terms don't change the complexity, nor do any multipliers, so there's no reason to write them out.

Since Θ(g) is a set, you would say that f(n) ∈ Θ(g).

NB: Many CS teachers, textbooks, and other resources muddy the waters by using imprecise notation. Lots of people say that f(n)=n3 is O(n3), rather than f(n)=n3 is in O(n3). They use = when they mean ∈.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
1

theta(g(n)) lies between O(g(n)) and omega(g(n)) if g(n) = 1000n^3 + n

first lets find O(g(n)) upper bound It could be n^3, n^4, n^5 but we choose the closest one which is O(n^3).

O(n^3) is valid because we can find a constant c such that for some value of n 1000n^3 + n < c.n^3

second lets see omega(g(n)) which is lower bound omega says f(n) > c.g(n) we can find a constant c such that 1000.n^3 + n > c.n^3

Now we have upper bound which is O(n^3) and lower bound which is omega(n^3). therefore we have theta which bounds both upper and lower using same function.

By rule : if f(n) = O(g(n)) and f(n) = omega(g(n)) therefore f(n) = theta(g(n))

1000.n^3 + n = theta(n^3)

Vikram Singh
  • 56
  • 1