I've recently learned about the Big Oh notation and heard that the following aren't true:

  1. $f(n)\in O(f(n)^2)$.
  2. Either $f(n)\in O(g(n))$ or $f(n)\in\Omega(g(n))$ or both.
  3. $f(n)\in\omega(g(n))$ implies $\log(f(n)) = \omega(\log(g(n))$.

I'm trying to find a good counter-example for each but it's proving to be a bit challenging. What would be a good one for these?

  • 1
    $\begingroup$ can you give more context? $\endgroup$
    – Joe
    Mar 19 '14 at 2:31
  • $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$
    – Raphael
    Mar 19 '14 at 8:13

For (1), take $f(n) = 1/n$.

For (2), take $f(n) = \begin{cases} 1 & n \text{ even} \\ n & n \text{ odd} \end{cases}$ and $g(n) = \sqrt{n}$.

For (3), take $f(n) = n^2$ and $g(n) = n$.


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