Question

$(\log n)!$ and $(\log \log n)!$ are polynomially bounded ? anybody can prove?

Answer 1

We have Stirling's approximation which says

$$\log n! = \Theta( n \log n)$$

So, $(\log n)! = e^{\log (\log n)!} \\=  \Theta \left(e^{ ( \log n \log \log n )}\right) \\=  \Theta \left( \left({e^{\log n}} \right) ^ {\log \log n}\right) \\= \Theta \left(n^{\log \log n}\right)$.

Hence, polynomially lower bounded but not upper bounded. For polynomial, we need $n^c$, where $c$ is a constant, which is not the case here.

$(\log \log n)! = e^{\log (\log \log n)!} \\=  \Theta \left(e^{ ( \log \log n \log \log \log n )}\right) \\=  \Theta \left(\left( {e^{\log \log n}} \right)^ {\log \log \log n} \right) \\= \Theta \left(\left(\log n\right)^{ \log \log \log n}\right) = O(n) \\ \left( \because n^{\log \log n} = O(e^{n}), \\ \text{ detailed at end, and replace }n \text{ with } \log n \right)  $.

Hence polynomially upper bounded.

---

$n^{\log \log n} = {e^{\log n}}^{\log \log n} \\= e^ {\log n \log \log n}  \\= O(e^ n)$

Comments

Explained at end, clear now?

---

How (logn)^logloglogn is equal to n. Please clear my doubt

---

@Arjun Sir,

You wrote the following in the last line for explanation:

$n^{loglogn}=e^{logn^{loglogn}}=e^{lognloglogn}=O(e^{n})$

But shouldn't it be $O(e^{logn})$