algorithm - When to use Big O instead of theta or little o -


a question asymptotic notation. i've seen lot of explanations of asymptotic notation say:

θ(...) analogous =

o(...) analogous <=

o(...) analogous <

which seem imply if f(n) = o(g(n)), either f(n) = θ(g(n)) or f(n) = o(g(n)).

is possible have f(n) = o(g(n)) such neither f(n) = θ(g(n)) nor f(n) = o(g(n))? if so, example of this? , if not, why ever use o(...) when θ(...) or o(...) stronger descriptors?

let f(n)=k!, when k smallest integer such n<=k!.

then f(n) not θ(n) (since f(k!+1)/(k!+1) tends infinity) neither o(n) (since f(k!)=k!), f(n)=o(n) (as f(n)<=n).


Comments

Popular posts from this blog

ios - MKAnnotationView layer is not of expected type: MKLayer -

ZeroMQ on Windows, with Qt Creator -

unity3d - Unity SceneManager.LoadScene quits application -