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 (a), $f(n)$ is neither $O(g_i(n))$ nor $\Omega(g_i(n))$.

$$ \begin{array}{ll} 2^{2^{n + 1}} & \\ 2^{2^n} & \\ (n + 1)! & \\ n! & \\ e^n & \\ n\cdot 2^n & \\ 2^n & \\ (3 / 2)^n & \\ (\lg n)^{\lg n} = n^{\lg\lg n} & \\ (\lg n)! & \\ n^3 & \\ n^2 = 4^{\lg n} & \\ n\lg n \text{ and } \lg(n!) & \\ n = 2^{\lg n} & \\ (\sqrt 2)^{\lg n}(= \sqrt n) & \\ 2^{\sqrt{2\lg n}} & \\ \lg^2 n & \\ \ln n & \\ \sqrt{\lg n} & \\ \ln\ln n & \\ 2^{\lg^*n} & \\ \lg^*n \text{ and } \lg^*(\lg n) & \\ \lg(\lg^*n) & \\ n^{1 / \lg n}(= 2) \text{ and } 1 & \end{array} $$

b. For example,

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

for all functions $g_i(n)$ in part (a), $f(n)$ is neither $O(g_i(n))$ nor $\Omega(g_i(n))$.