3-3 Ordering by asymptotic growth rates

a. Rank the following functions by order of growth; that is, find an arrangement $g_1, g_2, \ldots , g_{30}$ of the functions $g_1 = \Omega(g_2), g_2 = \Omega(g_3), \ldots, g_{29} = \Omega(g_{30})$. Partition your list into equivalence classes such that functions $f(n)$ and $g(n)$ are in the same class if and only if $f(n) = \Theta(g(n))$.

$$ \begin{array}{cccccc} \lg(\lg^{^*}n) \quad & \quad 2^{\lg^*n} \quad & \quad (\sqrt 2)^{\lg n} \quad & \quad n^2 \quad & \quad n! \quad & \quad (\lg n)! \\ (\frac{3}{2})^n \quad & \quad n^3 \quad & \quad \lg^2 n \quad & \quad \lg(n!) \quad & \quad 2^{2^n} \quad & \quad n^{1/\lg n} \\ \lg\lg n \quad & \quad \lg^* n \quad & \quad n\cdot 2^n \quad & \quad n^{\lg\lg n} \quad & \quad \lg n \quad & \quad 1 \\ 2^{\lg n} \quad & \quad (\lg n)^{\lg n} \quad & \quad e^n \quad & \quad 4^{\lg n} \quad & \quad (n + 1)! \quad & \quad \sqrt{\lg n} \\ \lg^*(\lg n) \quad & \quad 2^{\sqrt{2\lg n}} \quad & \quad n \quad & \quad 2^n \quad & \quad n\lg n \quad & \quad 2^{2^{n + 1}} \end{array} $$

b. Give an example of a single nonnegative function $f(n)$ such that for all functions $g_i(n)$ in part (1), $f(n)$ is neither $O(g_i(n))$ nor $\Omega(g_i(n))$.

a. Here is the ordering, where functions on the same line are in the same equivalence class, and those higher on the page are $\Omega$ of those below them:

$$ \begin{array}{ll} 2^{2^{n + 1}} & \\ 2^{2^n} & \\ (n + 1)! & \\ n! & \text{see justification 7} \\ e^n & \text{see justification 1} \\ n\cdot 2^n & \\ 2^n & \\ (3 / 2)^n & \\ (\lg n)^{\lg n} = n^{\lg\lg n} & \text{see identity 1} \\ (\lg n)! & \text{see justifications 2, 8} \\ n^3 & \\ n^2 = 4^{\lg n} & \text{see identity 2} \\ n\lg n \text{ and } \lg(n!) & \text{see justification 6} \\ n = 2^{\lg n} & \text{see identity 3} \\ (\sqrt 2)^{\lg n}(= \sqrt n) & \text{see identity 6, justification 3} \\ 2^{\sqrt{2\lg n}} & \text{see identity 5, justification 4}\\ \lg^2 n & \\ \ln n & \\ \sqrt{\lg n} & \\ \ln\ln n & \text{see justification 5} \\ 2^{\lg^*n} & \\ \lg^*n \text{ and } \lg^*(\lg n) & \text{see identity 7} \\ \lg(\lg^*)n & \\ n^{1 / \lg n}(= 2) \text{ and } 1 & \text{see identity 4} \end{array} $$

Much of the ranking is based on the following properties:

  • Exponential functions grow faster than polynomial functions, which grow faster than polylogarithmic functions.
  • The base of a logarithm doen't matter asymptotically, but the base of an exponential and the degree of a polynomial do matter.

We have the following $\textit{identities}$:

  1. $(\lg n)^{\lg n} = n^{\lg\lg n}$ because $a^{\log_b c} = c^{\log_b a}$.
  2. $4^{\lg n} = n^2$ because $a^{\log_b c} = c^{\log_b a}$.
  3. $2^{\lg n} = n$.
  4. $2 = n^{1 / \lg n}$ by raising identity 3 to the power $1 / \lg n$.
  5. $2^{\sqrt{2\lg n}} = n^{\sqrt{2 / \lg n}}$ by raising identity 4 to the power $\sqrt{2\lg n}$.
  6. $(\sqrt 2)^{\lg n} = \sqrt n$ because $(\sqrt 2)^{\lg n} = 2^{(1 / 2)\lg n} = 2^{\lg\sqrt n} = \sqrt n$.
  7. $\lg^*(\lg n) = (\lg^*n) - 1$.

The following $\textit{justifications}$ explain some of the rankings:

  1. $e^n = 2^n(e / 2)^n = \omega(n2^n)$, since $(e/2)^n = \omega(n)$.
  2. $(\lg n) \ne \omega(n^3)$ by taking logs: $\lg(\lg n) \ne \Theta(\lg n\lg\lg n)$ by Stirling's approximation, $\lg(n^3) = 3\lg n$. $\lg\lg n = \omega(3)$.
  3. $(\sqrt 2)^{\lg n} = \omega(2^{\sqrt{2\lg n}})$ by taking logs: $\lg(\sqrt 2)^{\lg n} = (1 / 2)\lg n,\lg 2^{\sqrt{2\lg n}} = \sqrt{2\lg n}$. $(1 / 2)\lg n = \omega(\sqrt{2\lg n})$.
  4. $2^{\sqrt{2\lg n}} = \omega(\lg^2 n)$ by taking logs: $\lg 2^{\sqrt{2\lg n}} = \sqrt{2\lg n},\lg\lg^2n = 2\lg\lg n$. $\sqrt{2\lg n} = \omega(2\lg\lg n)$.
  5. $\ln\ln n = \omega(2^{\lg^*n})$ by taking logs: $\lg 2^{\lg^* n} = \lg^*n$. $\lg\ln\ln n = \omega(\lg^*n)$.
  6. $\lg(n!) = \Theta(n\lg n)$ (equation $\text{(3.18)}$).
  7. $n \ne \Theta(n^{n + 1}e^{-n})$ by dropping constants and low-order terms in equation $\text{(3.17)}$.
  8. $(\lg n) \ne \Theta((\lg n)^{\lg n + 1 / 2} e^{-\lg n}$ by substituting $\lg n$ for $n$ in the previous justification. $(\lg n) \ne \Theta((\lg n)^{\lg n + 1 / 2}n^{-\lg e})$ because $a^{\log_b c} = c^{\log_b a}$.

b. The following $f(n)$ is nonnegative, and for all functions $g_i(n)$ in part (1), $f(n)$ is neither $O(g_i(n))$ nor $\Omega(g_i(n))$.

$$ f(n) = \begin{cases} 2^{2^{n + 2}} & \text{if $n$ is even}, \\ 0 & \text{if $n$ is odd}. \end{cases} $$