1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Rahul Dec 17 '16 at 15:16
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.