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.

  • $\begingroup$ The answer has been revised, so @YuvalFilmus's comment no longer applies. However, the answer doesn't really prove anything, because it makes assertions at the same level of conceptual difficulty as the thing that's supposed to be proven. It's like proving that $\pi>2$ by saying "Well, $\pi>3$ and $3>2$, QED." Anyone who's prepared to just accept that $\pi>3$ should have just accepted $\pi>2$ in the first place. $\endgroup$ – David Richerby Nov 16 at 0:24

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