3-3 Ordering by asymptotic growth rates

a. Rank the following fuctions vy oefer of growth. That is, find an arrangement $g_1,g_2,\dots,g_{30}$ of the functions satisfying $g_1=\Omega(g_2),g_2=\Omega(g_3),\dots ,g_{29}=\Omega(g_{30})$. Partion your list into equivalence classes such that functions $f(n)$ and $g(n)$ belong to the same class if and only if $f(n)$ = $\Theta g(n)$

$$ \begin{array}{} & \lg(\lg^{\ast}n) & 2^{\lg^{\ast}n} & (\sqrt {2})^{\lg n} & n^2 & n! & (\lg n)!\cr & (3/2)^n & n^3 & \lg^2n & \lg(n!) & 2^{2^n} & n^{1/\lg n}\cr & \ln\ln n & \lg^{\ast}n & n\cdot 2^n & n^{\lg\lg n} & \ln n & 1\cr & 2^{\lg n} & (\lg n)^{\lg n} & e^n & 4^{\lg n} & (n+1)! & \sqrt{\lg n}\cr & \lg^{\ast}(\lg n) & 2^{\sqrt{2 \lg n}}& n & 2^n& n\lg n & 2^{2^{n+1}}\cr \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))$.

a

$$ \begin{aligned} 2^{2^{n+1}}\cr 2^{2^n}\cr (n+1)!\cr n!\cr e^n\cr n\cdot 2^n\cr 2^n\cr (3/2)^n\cr n^{\lg\lg n} \And (\lg n)^{\lg n}\cr (\lg n)!\cr n^3\cr n^2 \And 4^{\lg n} \cr \lg(n!) \And n\lg n\cr 2^{\lg n} \And n\cr (\sqrt {2})^{\lg n}\cr 2^{\sqrt{2\lg n}}\cr \lg^2 n\cr \ln n\cr \sqrt{\lg n}\cr \ln\ln n\cr 2^{\lg^{\ast}n}\cr \lg^{\ast}n \And \lg^{\ast}(\lg n)\cr \lg(\lg^{\ast}n) \cr n^{1/\lg n}\And 1\cr \end{aligned} $$

b

$|\sin{n}|\cdot 2^{2^{2^{n+1}}}$