# $n^{2/3}$ dominates $n^{1/2}$, what would be the correct big O/Theta/Omega?

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

• Big $\Omega$ is the opposite of little o, not of big O. – almagest Jan 8 at 7:50
• @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. – Thomas Lesgourgues Jan 8 at 8:03
• Yes, it is unfortunate that Donald Knuth introduced a different meaning for Big $\Omega$, it makes it more or less unusable. – almagest Jan 8 at 8:05
• @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$. – Omnomnomnom Jan 8 at 8:11
• @Omnomnomnom by "opposite of big O" we mean only what you have stated : $f=O(g)$ iff $g=\Omega(f)$ – Thomas Lesgourgues Jan 8 at 10:12

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