Complexity analysis of a polynomial and a logarithmic exponential function

Question

I need to find the asymptotic relationship between the functions $f(n) = n^{100}$ and $g(n) = (log_2n)^{(1/2) \cdot log_2n}$.

I did the following to show that $f(n) = O(g(n))$:

$n^{100} \leq (log_2n)^{(1/2) \cdot log_2n} \impliedby 2^{n^{100}} \leq 2^{(log_2n)^{(1/2) \cdot {log_2n}}} \impliedby 2^{100 \cdot n} \leq n^{(1/2) \cdot log_2n} \impliedby 2^{2^{100 \cdot n}} \leq 2^{n^{(1/2) \cdot log_2n}} \impliedby 2^{200 \cdot n} \leq 2^{n \cdot (1/2) \cdot log_2n} \impliedby 200 \cdot n \leq (1/2) \cdot n \cdot log_2n \impliedby 200 \leq (1/2) \cdot log_2n \impliedby 400 \leq log_2n \impliedby n \geq 2^{400}$

However, my analysis seems to be incorrect, because when i plug the relevant numbers (some $n \geq 2^{400}$ into WolframAlpha, the inequality doesn't hold. I believe that I'm using some exponent properties wrong in my calculations, but I'm unable to spot them. Could you please elaborate on what part am I missing?

Thank you very much

Answer 1

You go from $2^{200 \cdot n} \leq 2^{n \cdot (1/2) \cdot \log_2 n}$ to $2^{100 \cdot n} \leq 2^{(1/2) \log_2 n}$ via an intermediate step. This can't be right as you have taken the square root of the left-hand side and the $n^\text{th}$ root of the right-hand side.

Perhaps more useful is this identity $$ a^b = (a)^b = (\mathrm{e}^{\ln a})^b = \mathrm{e}^{b \ln a} \text{.} $$ Using this on your original complicated function, I get $$ (\log_2 n)^{(1/2) \log_2 n} = \mathrm{e}^{(1/2) \log_2 n \log_2 \log_2 n} = n^{(1/2) \log_2 \log_2 n} \text{,} $$ which should help you with your asymptotic analysis and help you realize that $2^{400}$ might not be big enough to see the asymptotic behaviour.

Answer 2

Write for convenience $\exp_2(x)=2^x$. We have $a^z=(2^{\log_2 a})^z=\exp_2(z\log_2 a)$, hence $(\log_2 n)^{(1/2)\log_2 n}=\exp_2({1\over 2}\log_2 n\cdot \log_2 \log_2 n)$, whereas $n^{100}=$ $\exp_2(100\log_2 n)$. We have $100\log_2 n=o(\log_2 n\cdot \log_2\log_2 n)$, and therefore $n^{100}=\exp_2(100\log_2 n) =$ $o(\exp_2({1\over2}\log_2 n\cdot \log_2\log_2 n))$ $=o((\log_2 n)^{(1/2)\log_2 n}).$ This solves your problem.

As to what you did wrong, I don't quite see how $2^{200n} \leq 2^{n (1/2) \log_2n}$ implies $2^{2^{100n}} \leq 2^{n^{(1/2) \log_2n}}$. If we raise $2$ to the square root of the left hand side, we get $2^{2^{100n}}$; if we raise $2$ to the square root of the right hand side, we get $2^{2^{n(1/4)\log_2 n}}$, and that seems to be $2^{n^{n/4}}$.

Answer 3

$\log_2 f(n)=100 \log_2 n$ while $\log_2 g(n)=(1/2)(\log_2 n) \log_2 (\log_2 n)$ so for $n>2$ we have $$1-\frac {\log_2 f(n)}{\log_2 g(n)}=1-\frac {200}{ \log_2 (\log_2 n)}$$ which $\to 1$ as $n\to \infty.$

We have $f(n)=$o$(g(n))$, and, a fortiori, $f(n)=$O$(g(n)$), because $$\log_2f(n)/g(n)=\log_2 f(n)-\log _2g(n)=[-\log g_2(n)]\cdot [1-\frac {\log_2 f(n)}{\log_2 g(n)}\;]$$ which goes to $-\infty$ as $n\to \infty$ (because $-\log_2 g(n)\to -\infty$ and the other term $\to 1).$