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

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?

• Just because something is not polynomial doesn't prove that it grows faster than a polynomial. For example, $\sin n$ is not polynomial. // You have to show that, for any polynomial $n^k$, the function $n^{\log 4n}$ grows faster than it. – Rahul Dec 17 '16 at 15:16

$$n^k$$
Eventually, $\log4n$ will be greater than $k$, so,
$$n^k<n^{\log4n}\ \forall n>2^{k-2}$$
$$\implies n^k<<n^{\log4n}$$