search

Log Log Log

Thu, Apr 14, 2016 02:00 CEST

Tags: Identities, Inequalities, Analysis of Algorithms

Theorem

log⁡nlog⁡log⁡n!=Θ(n) \frac{\log n}{\log \log n}! = \Theta(n)

Proof

K2!=log⁡nlog⁡log⁡n2!=log⁡nlog⁡log⁡n!lim⁡K2→∞K2!=2πlog⁡nlog⁡log⁡n(log⁡nlog⁡log⁡ne)log⁡nlog⁡log⁡nlim⁡n→∞K2!=2πlog⁡nlog⁡log⁡n(log⁡nlog⁡log⁡ne)log⁡nlog⁡log⁡n=2πlog⁡nlog⁡log⁡n(log⁡nelog⁡log⁡n)log⁡nlog⁡log⁡n=2πlog⁡nlog⁡log⁡n2log⁡log⁡nlog⁡nlog⁡log⁡n2log⁡log⁡log⁡nlog⁡nlog⁡log⁡n2log⁡elog⁡nlog⁡log⁡n=2πlog⁡nlog⁡log⁡nnnlog⁡log⁡log⁡nlog⁡log⁡nnlog⁡elog⁡log⁡n=2π2log⁡log⁡n2log⁡log⁡log⁡nnnlog⁡log⁡log⁡nlog⁡log⁡nnlog⁡elog⁡log⁡n=2πnlog⁡log⁡nlog⁡nnlog⁡log⁡log⁡nlog⁡nnnlog⁡log⁡log⁡nlog⁡log⁡nnlog⁡elog⁡log⁡n=2πnlog⁡log⁡n2log⁡nnlog⁡log⁡log⁡n2log⁡nnnlog⁡log⁡log⁡nlog⁡log⁡nnlog⁡elog⁡log⁡n=2πnlog⁡log⁡n2log⁡nnlog⁡log⁡log⁡n2log⁡nnnlog⁡log⁡log⁡n+log⁡elog⁡log⁡n=2πn(log⁡log⁡n)22log⁡nlog⁡log⁡nnlog⁡log⁡nlog⁡log⁡log⁡n2log⁡nlog⁡log⁡nnn2log⁡nlog⁡log⁡log⁡n+2log⁡nlog⁡e2log⁡nlog⁡log⁡n=2πnn2log⁡elog⁡n+2log⁡nlog⁡log⁡log⁡n+log⁡log⁡nlog⁡log⁡log⁡n−(log⁡log⁡n)22log⁡nlog⁡log⁡n=2πnn2log⁡nlog⁡log⁡log⁡n2log⁡nlog⁡log⁡n=2πnnlog⁡log⁡log⁡nlog⁡log⁡n=2πn1−log⁡log⁡log⁡nlog⁡log⁡n \begin{aligned} K^2! &= \sqrt{\frac{\log n}{\log \log n}}^2! \\ &= \frac{\log n}{\log \log n}! \\ \lim_{K^2 \to \infty} K^2! &= \sqrt{2\pi \frac{\log n}{\log \log n}} \left( \frac{\frac{\log n}{\log \log n}}{e}\right)^\frac{\log n}{\log \log n} \\ \lim_{n \to \infty} K^2! &= \sqrt{2\pi \frac{\log n}{\log \log n}} \left( \frac{\frac{\log n}{\log \log n}}{e}\right)^\frac{\log n}{\log \log n} \\ &= \sqrt{2\pi \frac{\log n}{\log \log n}} \left( \frac{\log n}{e \log \log n}\right)^\frac{\log n}{\log \log n} \\ &= \sqrt{2\pi \frac{\log n}{\log \log n}} \frac{2^{\log \log n\frac{\log n}{\log \log n}}}{2^{\log \log \log n\frac{\log n}{\log \log n}} 2^{\log e\frac{\log n}{\log \log n}} } \\ &= \sqrt{2\pi \frac{\log n}{\log \log n}} \frac{n}{n^{\frac{\log \log \log n}{\log \log n}} n^{\frac{\log e}{\log \log n}} } \\ &= \sqrt{2\pi \frac{2^{\log \log n}}{2^{\log \log \log n}}} \frac{n}{n^{\frac{\log \log \log n}{\log \log n}} n^{\frac{\log e}{\log \log n}} } \\ &= \sqrt{2\pi \frac{n^{\frac{\log \log n}{\log n}}}{n^{\frac{\log \log \log n}{\log n}}}} \frac{n}{n^{\frac{\log \log \log n}{\log \log n}} n^{\frac{\log e}{\log \log n}} } \\ &= \sqrt{2\pi} \frac{n^{\frac{\log \log n}{2\log n}}}{n^{\frac{\log \log \log n}{2\log n}}} \frac{n}{n^{\frac{\log \log \log n}{\log \log n}} n^{\frac{\log e}{\log \log n}} } \\ &= \sqrt{2\pi} \frac{n^{\frac{\log \log n}{2\log n}}}{n^{\frac{\log \log \log n}{2\log n}}} \frac{n}{n^{\frac{\log \log \log n + \log e}{\log \log n}} } \\ &= \sqrt{2\pi} \frac{n^{\frac{(\log \log n)^2}{2\log n\log\log n}}}{n^{\frac{\log \log n \log \log \log n}{2\log n \log \log n}}} \frac{n}{n^{\frac{2 \log n \log \log \log n + 2 \log n \log e}{2\log n \log \log n}} } \\ &= \sqrt{2\pi} \frac{n}{n^{\frac{2 \log e \log n + 2 \log n \log \log \log n + \log \log n \log \log \log n - (\log \log n)^2}{2\log n \log \log n}} } \\ &= \sqrt{2\pi} \frac{n}{n^{\frac{2 \log n \log \log \log n}{2\log n \log \log n}} } \\ &= \sqrt{2\pi} \frac{n}{n^{\frac{\log \log \log n}{\log \log n}} } \\ &= \sqrt{2\pi} n^{1 - \frac{\log \log \log n}{\log \log n}} \\ \end{aligned}