Ordering Complexity Classes: Problem 3–3 a, page 58 Cormen, Leiserson, Rivest, Stein: Second Edition

We write f(n) ≡ g(n) to mean that f(n) = Θ(g(n), and we write f(n) ≪ g(n) to mean that f(n) = O(g(n)) but g(n) ≠ Θ(g(n)). Constant: 1 ≡ n^{1/ lg n} = 2 ≪ I don’t know a class name for these: lg(lg^{∗} n) ≪ lg^{∗} n ≡ lg^{∗} (lg n) ≪ 2^{lg^{∗} n} ≪ I don’t know a class name for these: ln ln n ≪ Polylogarithmic: \sqrt{lg n} ≪ ln n ≪ lg^{2} n ≪ Superpolylogarithmic and subpolynomial: 2^{\sqrt{2 lg n}} ≪ Polynomial: (\sqrt{2})^{lg n} = \sqrt{n} ≪ n = 2^{lg n} ≪ n lg n ≡ lg (n!) ≪ n^{2} = 4^{lg n} ≪ n^{3} ≪ Superpolynomial and subexponential: (lg n)! ≪ n^{lg lg n} = (lg n)^{lg n} ≪ Exponential: (\frac{3}{2})^{n} ≪ 2^{n} ≪ n · 2^{n} ≪ e^{n} ≪ n! ≪ (n + 1)! ≪ Double Exponential: 2^{2^{n}} ≪ 2^{2^{n+1}}