# log, exponential and Big-Theta

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?

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.
• $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$) – Clement C. Jan 24 '17 at 14:27
• 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. – Clement C. Jan 24 '17 at 14:29