2
$\begingroup$

If I have $f(n)=n^{2/3}$ and $g(n) = n^{1/2}$, then I believe their big $O$'s are $O(n^{2/3})$ and $O(n^{1/2})$.

This is where I'm a little confused. I need to find if $f=O(g)$, $f=\Omega(g)$ or $f=\Theta(g)$.

I know that $f$ dominates $g$, so they have different big $O$'s and so $f\neq O(g)$.

... and that's as far as I'm able to get.


I'm trying to grasp the concepts of big $\Theta$ and $\Omega$ but my book is kind of confusing. It says that $f=\Omega(g)$ means $g=O(f)$, which I thought meant that if $f$ and $g$ have the same big $O$ then $f=\Omega(g)$ and $g=\Omega(f)$, but now I'm not so sure. I think this contradicts what I've read about big $\Omega$ being a lower bound - the opposite of big $O$, so I'm not entirely certain and I was hoping someone could clarify.

And I understand that big $\Theta$ represents both $f=O(g)$ and $f=\Omega(g)$, which places it between the two and is a tight bound, but I'm not really sure how to find if a function is big $\Theta$ - probably because I'm struggling understanding big $\Omega$

$\endgroup$
  • $\begingroup$ Big $\Omega$ is the opposite of little o, not of big O. $\endgroup$ – almagest Jan 8 at 7:50
  • $\begingroup$ @almagest that actually depends. It is detailled in the table provided as link in the answer. Personally I have seen used much more often as opposite of big O. $\endgroup$ – Thomas Lesgourgues Jan 8 at 8:03
  • $\begingroup$ Yes, it is unfortunate that Donald Knuth introduced a different meaning for Big $\Omega$, it makes it more or less unusable. $\endgroup$ – almagest Jan 8 at 8:05
  • $\begingroup$ @Thomas I don't know what either of you two are talking about. I have yet to see $\Omega$ used to mean "the opposite of big $O$". Neither definition of $\Omega$ from the table means the opposite of big $O$. $\endgroup$ – Omnomnomnom Jan 8 at 8:11
  • $\begingroup$ @Omnomnomnom by "opposite of big O" we mean only what you have stated : $f=O(g)$ iff $g=\Omega(f)$ $\endgroup$ – Thomas Lesgourgues Jan 8 at 10:12
1
$\begingroup$

If $f=\Theta(g)$ then $f=O(g)$, as the constant in the latter relation can be taken to be $1$. Since the latter is false here, $f\ne\Theta(g)$.

Now consider $$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\lim_{n\to\infty}\frac{n^{2/3}}{n^{1/2}}=\lim_{n\to\infty}n^{1/6}=\infty$$ Since this limit is positive (the infiniteness does not matter), $f=\Omega(g)$.

$\endgroup$
1
$\begingroup$

Intuitively, $f = O(g)$ is something like "$f \leq g$", and $f = \Omega(g)$ is something like "$f \geq g$". Note for instance that we have $f = O(g)$ iff $g = \Omega(f)$.

This table summarizes the situation clearly. In particular, I tend to think in terms of the right-hand column (for our purposes, we can treat the $\limsup$ and $\liminf$ as if they were just a $\lim$). In your case, we have $$ \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty. $$ So, we see that $f = \Omega(g)$, but $f \neq O(g)$ and $f \neq \Theta(g)$.

If $\lim_{n \to \infty}\frac{f(n)}{g(n)}$ exists, then we will have $f = \Theta(g)$ if and only if the limit is finite but non-zero.

$\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.