2.25

Lowest → Highest growth:
[math]2^{\log n^{2}} = n^{2}\;<\;n^{4}\binom{n}{n-4}=Θ(n^{8})\;<\;(\log n)^{\log n}=n^{\log\log n}\;<\;n^{(\log n)^{2}}\;<\;2^{\log^{4} n}\;<\;n!\;<\;n^{n}\;=\;Θ\!\Bigl(\displaystyle\sum_{i=1}^{n} i^{i}\Bigr)[/math]

Sketch of comparisons (let [math]m=\log n[/math]):
• [math]2^{\log n^{2}}=n^{2}[/math] is polynomial.
• [math]n^{4}\binom{n}{n-4}\sim n^{4}\cdot n^{4}/24=Θ(n^{8})[/math] (still polynomial).
• [math](\log n)^{\log n}=e^{m\log m}=n^{\log\log n}[/math] eventually beats every fixed-degree polynomial.
• [math]n^{(\log n)^{2}}=e^{m^{2}\log n}=e^{m^{3}}[/math] so its exponent [math]m^{3}[/math] outgrows the preceding [math]m\log m[/math].
• [math]2^{\log^{4} n}=e^{\Theta(m^{4})}[/math] has exponent [math]m^{4}[/math] > [math]m^{3}[/math].
• Stirling gives [math]n!\sim e^{n\log n-n}[/math]; since [math]n\log n\gg m^{4}[/math], [math]n![/math] dominates all previous functions.
• [math]n^{n}=e^{n\log n}[/math] is larger than [math]n![/math] by a factor [math]e^{n}[/math].
• The sum [math]\sum_{i=1}^{n} i^{i}[/math] is Θ([math]n^{n}[/math]) because the last term [math]n^{n}[/math] dwarfs the rest, so it shares the same order as [math]n^{n}[/math].
Hence the ordering above, with [math]n^{n}[/math] and [math]\sum i^{i}[/math] in the same Θ-class.

Back to Chapter 2