Big-Oh of exponent of exponent

Question

How does one whether an exponent of an exponent is the big-Oh of the other?

For example, if I have $a^{b^n}$ and $b^{a^n}$, how would i determine and prove which is a big oh of another? I'm thinking that the one with the bigger base grows faster so the smaller base is big-Oh/lower bound of the other?

Answer 1

We could try to compute

$$L_1=\lim_{n\to \infty} \frac{a^{b^n}}{b^{a^n}}\text{,}$$ but it is harder than computing the limit

$$L_2=\lim_{n\to \infty} \log \left(\frac{a^{b^n}}{b^{a^n}} \right) = \lim_{n\to \infty} \left(\log (a^{b^n}) - \log (b^{a^n})\right)\text{.}$$

Since $\log x^y = y\log x$ for all $x,y>0$, it holds that

$$L_2=\lim_{n\to \infty} \left(b^n \log a -a^n \log b \right)\text{.}$$

Now, consider all the cases: $1<a<b$, $a<1<b$, $a=b<1$, ...

• If $L_2=\infty$, then note that $L_1 = \infty$ and prove $b^{a^n}\in\mathcal{O}(a^{b^n})$.
• If $L_2=-\infty$, then note that $L_1 = 0$ and prove that $a^{b^n}\in\mathcal{O}(b^{a^n})$.
• If $-\infty<L_2<\infty$, then note that $-\infty<L_1<\infty$ and prove that $b^{a^n}\in\mathcal{O}(a^{b^n})$ and $a^{b^n}\in\mathcal{O}(b^{a^n})$.