This question is from CLRS (3rd Edition).

So, I know that this is true, but I can't seem to prove it. My approach was the following:

Let $f(n) = o(g(n)) \Rightarrow 0 \le f(n) < c_2g(n)$ for some $c_2 > 0$ and for all $n \ge n_1 \ge 0$

Similarly, $f(n) = \omega(g(n)) \Rightarrow 0 \le c_1g(n) < f(n)$ for some $c_1 > 0$ and for all $n \ge n_2 \ge 0 $

Therefore, $0 \le c_1g(n) < f(n) < c_2 g(n)$

But this can be true for $f(n) = 2n$ and $g(n) = n$ and $c_1 = 1$, $c_2 = 3$, and $n_1 = n_2 = 1$

So what exactly am I not picking up?


1 Answer 1


What is wrong is your definition of $o$ and $\omega$.

$f\in o(g)$ if and only if $f(n) = h(n)g(n)$ with $h(n) \underset{n\rightarrow +\infty}{\longrightarrow}0$.

$f\in \omega(g)$ if and only if $g\in o(f)$.

What you used as definition are $\mathcal{O}$ and $\Omega$ (which are different).

  • $\begingroup$ The definition I used are given in CLRS. o-notation and ω-notation $\endgroup$ Mar 7 at 13:36
  • 1
    $\begingroup$ In this definition, the property $f(n) < c g(n)$ must be true for ANY $c>0$, not for SOME $c>0$. The quantification is universal, not existential. $\endgroup$
    – Nathaniel
    Mar 7 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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