CODEWITHSUNDEEP
algorithm
Jurgen
Jurgen

Reputation: 347

Why is Big Theta in the set Big O but not the other way around for the same function?

I'm reading through my algorithms text and it states:

enter image description here

But shouldn't the vice verse be true as well, so long as the function g(n) is the same in both cases?

I understand why it wouldn't work for different functions i.e n^2 and n. But for the same function couldn't an arbitrarily smaller and larger constant be used to surround O(g(n)) to make it asymptotically tight?

Upvotes: 1

Views: 358

Answers (1)

hbejgel
hbejgel

Reputation: 4837

The vice verse is not necessarily true since O notation establishes an upper bound for the function's complexity while Theta establishes both an upper and lower bound.

For example, for f(x) = x² you can say f(x) = O(x³) since x³ is indeed an upper bound for x² but you cannot say f(x) = ϴ(x³) since x³ is not a lower bound for x².

Take a look here for the precise definitions of O and ϴ notations

Upvotes: 3

Related Questions