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

Question

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$

Answer 1

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

Answer 2

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.