a. Rank the following functions by order of growth; that is, find an arrangement \(g_1, g_2,...,g_{30}\) of the functions satisfying \(g_1 = \Omega(g_2), g_2 = \Omega(g_3),...,g_{29} = \Omega(g_{30}).\) Partition our 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))\).

\[\newcommand\S{\Rule{0pt}{1em}{1em}} \begin{array}{cccccccc} \lg(\lg^* n) \S & 2^{\lg^* n} \S & (\sqrt{2})^{\lg n} \S & n^2 \S & n! \S & (\lg n)! \\ \left(\frac{3}{2} \right)^n \S & n^3 \S & \lg^2 n \S & \lg(n!) \S & 2^{2^n} \S & n^{1 / \lg n} \\ \ln \ln n \S & \lg^* n \S & n \cdot 2^n \S & n^{\lg \lg n} \S & \ln n \S & 1 \\ 2^{\lg n} \S & (\lg n)^{\lg n} \S & e^n \S & 4^{\lg n} \S & (n + 1)! \S & \sqrt{\lg n} \\ \lg^*(\lg n) \S & 2^{\sqrt{2 \lg n}} \S & n \S & 2^n \S & n \lg n \S & 2^{2^{n+1}} \\ \end{array}\]

As justification for \(n^{\lg \lg n} = (\lg n)^{\lg n}\) we use the identities \(a = b^{\log_ba}\) and \(a^{\log_bc} = c^{\log_ba}\) to generate this equality: \(n^{\lg \lg n} = (2^{\lg n})^{\lg \lg n} = (\lg n)^{\lg(2^{\lg n})} = (\lg n)^{\lg n}\)

As justification for \(n^2 = 4^{\lg n}\) we use the identities \((a^m)^n = a^{mn}\) and \(a^{\log_bc} = c^{\log_ba}\) to generate this equality: \(4^{\lg n} = (2^2)^{\lg n} = n^{\lg (2^2)} = n^2\). (A similar justification is used for \(n = 2^{\lg n}\))

\[\boldsymbol{\Theta(2^{2^{n+1}})} : 2^{2^{n+1}}\] \[\boldsymbol{\Theta(2^{2^n}}) : 2^{2^n}\] \[\boldsymbol{\Theta((n + 1)!)} : (n + 1)!\] \[\boldsymbol{\Theta(n!)} : n!\] \[\boldsymbol{\Theta(e^n)} : e^n\] \[\boldsymbol{\Theta(n \cdot 2^n)} : n \cdot 2^n\] \[\boldsymbol{\Theta(2^n)} : 2^n\] \[\boldsymbol{\Theta\left(\left(\frac{3}{2} \right)^n\right)} : \left(\frac{3}{2} \right)^n\] \[\boldsymbol{\Theta((\lg n)^{\lg n})} : n^{\lg \lg n} = (\lg n)^{\lg n}\] \[\boldsymbol{\Theta((\lg n)!)} : (\lg n)!\] \[\boldsymbol{\Theta(n^3)} : n^3\] \[\boldsymbol{\Theta(n^2)} : n^2 = 4^{\lg n}\] \[\boldsymbol{\Theta(n \lg n)} : n \lg n, \ lg(n!)\] \[\boldsymbol{\Theta(n)} : n = 2^{\lg n}\] \[\boldsymbol{\Theta(n^{\lg \sqrt{2}})} : (\sqrt{2})^{\lg n}\] \[\boldsymbol{\Theta(2^{\lg n})} : 2^{\sqrt{2 \lg n}}\] \[\boldsymbol{\Theta(\lg n \lg n)} : \lg^2 n\] \[\boldsymbol{\Theta(\ln n)} : \ln n\] \[\boldsymbol{\Theta(\sqrt{\lg n})} : \sqrt{\lg n}\] \[\boldsymbol{\Theta(\ln \ln n)} : \ln \ln n\] \[\boldsymbol{\Theta(2^{\lg^* n})} : 2^{\lg^* n}\] \[\boldsymbol{\Theta(\lg^* n)} : \lg^* n, \ \lg^*(\lg n)\] \[\boldsymbol{\Theta(\lg( \lg^* n))} : \lg( \lg^* n)\] \[\boldsymbol{\Theta(1)} : 1 = n^{1 / \lg n}\]

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))\).

\[f(n) = (\sin(n) + 1) \cdot 3^{3^{n+1}}\]

In previous exercises we’ve seen how the oscillation of the sin function tends to wreck asymptotic boundaries. So we take the usual \(\sin\) function and then add 1 to the output. This makes it non-negative to satisfy the constrains of the problem. We also need to make sure that it isn’t immediately outpaced by the largest function in our set of functions, so we then multiply it by a function that is guaranteed to be even larger. This gives us a function that oscillates between \(0\) and some ridiculously high number that is guaranteed to be the largest value when compared to our functions. Therefore, \(f(n) \neq O(g_i(n))\) and \(f(n) \neq \Omega(g_i(n))\)