Show that logn is not polynomially bounded but loglogn is po

Show that [logn]! is not polynomially bounded but [loglogn]! is polyno-mially bounded

Solution

I myself don\'t know the exact answer but I do find answer of it on Quora. May be it helps you.

Let A1=logn!A1=logn!,   A2=lg(lgn)!A2=lg(lgn)! or  A1=logn!A1=logn!, A2=lg(lgn)!A2=lg(lgn)! or  A1,A2A1,A2 are corresponding expressions in terms of   -function.

I\'m not going to be rigorous either.  

You have obviously k!<kkk!<kk for kN2.kN2.

It implies for n0n0 that  A2<lg(lg(n))lg(lg(n))=10lg(lg(n))lg(lg(lg(n))).A2<lg(lg(n))lg(lg(n))=10lg(lg(n))lg(lg(lg(n))).

On the other hand, n=10lg(n)n=10lg(n).

So you can just compare exponents lg(n)lg(n) and  lg(lg(n))lg(lg(lg(n)))lg(lg(n))lg(lg(lg(n))) for n0.n0.

It amounts to comparing  NN and lgNlg(lgN)lgNlg(lgN) for  N0.N0.

Now I think the answer is obvious, since  lgN<NlgN<N for any R>0R>0 and  N0.N0.Thus A2A2 is polynomially bounded.

Using  Stirling\'s approximation you can analogously treat the case of A1.A1. Basically, it will boil down to the comparison of  elognlog(logn)elognlog(logn) and emlogn,emlogn, where  mm is a constant (a power of some polynomial). So  A1A1 is  not polynomially bounded