Does $n^{log4n}$ grow faster than a polynomial?

Question

I was wondering if it is easy to prove. My thoughts

$$2^{logn^{log(4n)}} = 2^{log(4n)logn} = (4n)^{logn}$$

which is not polynomial. Is that correct?

Answer 1

Yes, but your reasoning is incorrect. Just because something is not a polynomial does not mean it will grow faster than it. Consider the following polynomial:

$$n^k$$

Eventually, $\log4n$ will be greater than $k$, so,

$$n^k<n^{\log4n}\ \forall n>2^{k-2}$$

$$\implies n^k<<n^{\log4n}$$