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?

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. — , Dec 17 '16 at 15:16

score 1 · Accepted Answer · answered Dec 17 '16 at 15:17

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}$$

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

1 Answers1