This question already has an answer here:

The following question is in my homework:

Is the statement $f(n) = O(g(n))$ true, when $f(n) = n/2 + 4$ and $g(n) = \sqrt{n} + 2\log_2 n + 3$?

I understand how $f(n)$ is the upper bound of $g(n)$. However, I am unsure how to prove it mathematically.


marked as duplicate by David Richerby, Evil, Discrete lizard Sep 12 at 14:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


f(n)=$\theta(n)$ while g(n)=O(n^(1/2)) so the statment is not true.

  • 1
    $\begingroup$ Since Big O is just an upper bound, there is no contradiction. For example, if $f(n) = g(n) = \sqrt{n}$ then it is also the case that $f(n) = O(n)$ while $g(n) = O(\sqrt{n})$, although $f(n) = O(g(n))$ does hold. $\endgroup$ – Yuval Filmus Sep 12 at 15:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.