1
$\begingroup$

Problem description

I am trying to understand the first example of Big-Oh notation in Computational Complexity:A Modern Approach page 9.

If $f(n) = 100nlogn$ and $g(n) = n^2$ then we have the relations $f = O(g)$, $g = Ω(f)$, $f = o(g)$, $g = ω(f)$.


I understood why $f = O(g)$ and $f = o(g)$ . As for the rest I didn't. For instance in order for $g$ to be equal to $Ω(f)$ we must have $g = O(f)$.


Question

How can we prove that $g = O(f)$ and $g=o(f)$?

$\endgroup$
1
$\begingroup$

I think you have the wrong definition for $\Omega$. When we write $g=Ω(f)$, informally this means that $g$ is bounded below by ${\displaystyle f}$ asymptotically. So, it is basically just the reverse way of saying $f=O(g)$, which means that $|f|$ is bounded above by ${\displaystyle g}$ (up to constant factor) asymptotically.

What you are describing is closest to the definition of Big theta $\Theta$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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