CODEWITHSUNDEEP
algorithmbig-oasymptotic-complexitylittle-o
A Nortonsmith
A Nortonsmith

Reputation: 166

When to use Big O instead of theta or little o

A question about asymptotic notation. I've seen a lot of explanations of asymptotic notation say:

θ(...) is analogous to =

O(...) is analogous to <=

o(...) is analogous to <

Which would seem to imply that if f(n) = O(g(n)), then either f(n) = θ(g(n)) or f(n) = o(g(n)).

Is it possible to have f(n) = O(g(n)) such that neither f(n) = θ(g(n)) nor f(n) = o(g(n))? If so, what is an example of this? And if not, then why would we ever use O(...) when θ(...) or o(...) are stronger descriptors?

Upvotes: 0

Views: 750

Answers (1)

asaelr
asaelr

Reputation: 5456

Let f(n)=k!, when k is the smallest integer such that n<=k!.

Then f(n) is not θ(n) (since f(k!+1)/(k!+1) tends to infinity) neither is o(n) (since f(k!)=k!), but clearly f(n)=O(n) (as f(n)<=n).

Upvotes: 1

Related Questions