# How to justify $f(n) = O(g(n))$ [duplicate]

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.

• When all else fails, use the definitions. – Yuval Filmus Sep 11 at 19:02
• What is big O? – vladimir Sep 12 at 6:00
• – Yuval Filmus Sep 12 at 7:28

## 1 Answer

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

• 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. – Yuval Filmus Sep 12 at 15:07