CODEWITHSUNDEEP
algorithmtime-complexitycomplexity-theoryasymptotic-complexitybig-o
JungleJeem
JungleJeem

Reputation: 51

Clarification for Theta notation in complexity analysis. Θ(g)

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)?

Upvotes: 1

Views: 156

Answers (2)

Vikram Singh
Vikram Singh

Reputation: 56

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)

Upvotes: 1

John Kugelman
John Kugelman

Reputation: 361729

Θ(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 ∈.

Upvotes: 1

Related Questions