0

Let $f(n) = (\log_2n)^{\log_2n}$ and $g(n) = 2^{(\log_2n)^2} $

I want to show that $f(n) \in o(g(n))$.

I guess it makes intuitive sense if we perform a a substitution $z = \log_2n$ we get $\lim_{z \to \infty} \frac{z^z}{2^{z^2}}$ which I remember as converging to $0$. But I'm not sure exactly why. How do you prove this rigorously?

I guess taking derivatives comes to mind which gets me $\frac{d}{dz}z^z = z^z(\log z+1)$ and $\frac{d}{dz}2^{z^2} = 2^{z^2}2z\log(2) $ which isn't that helpful for me.

ghthorpe
  • 1,507

1 Answers1

2

Note that for any number $n$, $n=2^{\log(n)}$. So $\log(n)=2^{\log(\log(n))}$. Let's plug this into $f$:

$$f(n)=(\log(n))^{\log(n)}=\left( 2^{\log(\log(n))} \right)^{\log(n)}=2^{\log(\log(n))\cdot\log(n)} $$

So $f$ is an exponential function with $\log(\log(n))$ in the exponent, whereas $g$ is an exponential function with $\log(n)^2$ in the exponent. Clearly $g$'s exponent grows faster, so $g$ grows faster. Why does $\log(\log(n))$ grow faster than $\log(n)$? Well, for large $n$, we have

$$\log(n)>\log(\log(n))\\\text{so: }\log(n)\cdot\log(n) > \log(\log(n))\cdot \log(n) $$

Lieuwe Vinkhuijzen
  • 653
  • 4
  • 10