Когда использовать Big O вместо Theta или Little O

Question

Вопрос об асимптотической записи. Я видел много объяснений асимптотической записи:

θ(...) аналогично =

O(...) аналогично <=

o(...) аналогично <

Что может показаться, что если f(n) = O(g(n))то либо f(n) = θ(g(n)) или же f(n) = o(g(n)),

Возможно ли иметь f(n) = O(g(n)) такой, что ни f(n) = θ(g(n)) ни f(n) = o(g(n))? Если да, то каков пример этого? А если нет, то зачем нам использовать O(...) когда θ(...) или же o(...) сильные дескрипторы?

Answer 1

Позволять f(n)=k!, когда k наименьшее целое число такое, что n<=k!,

затем f(n) не является θ(n) (поскольку f(k!+1)/(k!+1) стремится к бесконечности) o(n) (поскольку f(k!)=k!), но четко f(n)=O(n) (как f(n)<=n).