3

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$

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

2 Answers2

2

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

Parcly Taxel
  • 103,344
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.

Ben Grossmann
  • 225,327