3
$\begingroup$

The question is simple:

$$ (\log_2 n)^ke^{(c+o(1))(\log_2 n)^{1/3}(\log_2(\log_2(n)))^{2/3}} \text{ is } \Theta\left(e^{(c+o(1))(\log_2 n)^{1/3}(\log_2(\log_2(n)))^{2/3}} \right) $$

I don't understand why this is true. I definitely understand that the exponential growth is so much bigger that it "swallows" up the log growth, but from my understanding, $f$ is $\Theta(g)$ if and only if it is $\Omega(g)$ and $O(g)$.

But, one of the definition I've found in multiple places of big-Oh is that the limit when $n$ goes to infinity of $f/g$ must be anything but infinity. But if we compute the limit to infinity of these two functions, we definitely go to infinity, given the fact that the exponential part cancels out in both terms.

What trick am I missing?

$\endgroup$
4
$\begingroup$

The part you are missing is the $o(1)$ in the exponent. It is not the same in both cases, so things do not cancel out as you thought.

$$\begin{align} (\log_2 n)^k e^{(c+o(1))(\log_2 n)^{1/3} (\log_2\log_2 n)^{1/3}} &= e^{(c+o(1))(\log_2 n)^{1/3} (\log_2\log_2 n)^{1/3}+k\log \log_2 n}\\ &= e^{\left(c+o(1)+\frac{k\log \log_2 n}{(\log_2 n)^{1/3} (\log_2\log_2 n)^{1/3}}\right)(\log_2 n)^{1/3} (\log_2\log_2 n)^{1/3}} \end{align}$$ and since $$ \frac{k\log \log_2 n}{(\log_2 n)^{1/3} (\log_2\log_2 n)^{1/3}} \xrightarrow[n\to\infty]{} 0 $$ it is $o(1)$ as well, and we do have $$ o(1)+\frac{k\log \log_2 n}{(\log_2 n)^{1/3} (\log_2\log_2 n)^{1/3}} =o(1) $$ when $n\to\infty$. But this is in some sense a $o(1)$ "different (bigger) than" that on the original LHS.

To be honest, even the $\Theta(\cdot)$ is unnecessary. Remove it, and the statement is still true. The asymptotics are taken care of by the $o(1)$ in the exponent.

$\endgroup$
  • $\begingroup$ Thanks a lot for the explanation. I does make sense but I'm lost with the meaning of the o(1) here. I mean, don't understand how the o(1) makes a difference here -- though I do exactly understand how you put the log in the exponential form and how it makes sense that it disappears. So the part I don't get is why the o(1) is important in that process? $\endgroup$ – el-flor Jan 24 '17 at 14:23
  • $\begingroup$ $o(1)$ "hides" any quantity which goes to $0$ as $n\to\infty$. So, for instance in the LHS is could very well stand for $\frac{1}{\log\log\log\log\log n}$, and on the RHS stand for $\frac{1}{\log\log\log\log\log n}+ \frac{k\log \log_2 n}{(\log_2 n)^{1/3} (\log_2\log_2 n)^{1/3}}$. (Note that the second i s much bigger than the first, even though they both go to $0$) $\endgroup$ – Clement C. Jan 24 '17 at 14:27
  • $\begingroup$ For instance, $n e^n = e^{n+\log n} = e^{n+o(n) = e^{(1+o(1)n}}$ and $e^{\sqrt{n}}e^n = e^{n+\sqrt{n}} = e^{n+o(n)} = e^{(1+o(1))n}$. Both are $e^{(1+o(1))n}$, although the second is much bigger than the first. $\endgroup$ – Clement C. Jan 24 '17 at 14:29
  • $\begingroup$ Amazing. Thank you so much for the help. $\endgroup$ – el-flor Jan 24 '17 at 14:35
  • $\begingroup$ You're welcome! $\endgroup$ – Clement C. Jan 24 '17 at 14:35

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.