2.23

Ascending growth order ( ≺  = “grows strictly slower than”,  ≈  = “same asymptotic order”):
[math]\lg\!\lg n[/math] ≺ [math]\lg n[/math] ≺ [math](\!\lg n)^2[/math] ≺ [math]\sqrt n[/math] ≺ [math]n[/math] ≺ [math]n\lg n[/math] ≺ [math]n^{1+\varepsilon}\;(0<\varepsilon<1)[/math] ≺ [math]n^2 \;\approx\; n^2+\lg n[/math] ≺ [math]n^3[/math] ≺ [math]n-n^3+7n^5\;\;(\!\!\sim n^5)[/math] ≺ [math]2^{n-1}\;\approx\;2^n[/math] ≺ [math]e^n[/math] ≺ [math]n![/math]

Back to Chapter 2