Indicate, for each pair of expressions \((A,B)\) in the table below, whether \(A\) is \(O\), \(o\), \(\Omega\), \(\omega\), or \(\Theta\) of \(B\). Assume that \(k \geq 1\), \(\epsilon > 0\), and \(c > 1\) are constants.

\[\newcommand\T{\Rule{0pt}{1em}{.3em}} \begin{array}{|c|c|c|c|c|c|c|c|} \hline & A & B & O & o & \Omega & \omega & \Theta \\ \hline \textbf{a.} \T & \lg^k n \T & n^\epsilon \T & \textrm{Yes} \T & \textrm{Yes} \T & \textrm{No} \T & \textrm{No} \T & \textrm{No} \\ \hline \textbf{b.} \T & n^k \T & c^n \T & \textrm{Yes} \T & \textrm{Yes} \T & \textrm{No} \T & \textrm{No} \T & \textrm{No} \\ \hline \textbf{c.} \T & \sqrt{n} \T & n^{\sin n} & \textrm{No} & \textrm{No} & \textrm{No} & \textrm{No} & \textrm{No} \\ \hline \textbf{d.} \T & 2^n \T & 2^{\frac{n}{2}} \T & \textrm{No} & \textrm{No} & \textrm{Yes} & \textrm{Yes} & \textrm{No} \\ \hline \textbf{e.} \T & n^{\lg c} \T & c^{\lg n} \T & \textrm{Yes} & \textrm{No} & \textrm{Yes} & \textrm{No} & \textrm{Yes} \\ \hline \textbf{f.} \T & \lg{n!} \T & \lg{n^n} \T & \textrm{Yes} & \textrm{No} & \textrm{Yes} & \textrm{No} & \textrm{Yes} \\ \hline \end{array}\]

I have included informal discussions of how I reached the answers in this table.

a. Note that \(\lg^kn = (\lg n)^k\). Intuitively, because both \(k\) and \(\epsilon\) are constants, it must be the case that \(B\) is a strong upper bound of \(A\).

b. \(A\) is a variable to a constant power while \(B\) is a constant to a variable power. It is immediately clear that \(B\) represents a strong upper bound of \(A\).

c. \(A\) slowly but steadily increases while \(B\) actually oscilates between \(n^{-1}\) and \(n^{1}\) which means \(A\) is not asymptotically bound by \(B\) at all.

d. \(B\) intuitively represents the same function as \(A\) with a lower exponent, therefore it represents a strong lower bound of \(A\).

e. Based on the identity \(a^{\log_bc} = c^{\log_ba}\) these two functions are asymptotically equivalent.

f. This one threw me for a loop because intuitively it really seems like \(B\) grows much faster than \(A\) when in fact they are asymptotically equivalent. Consider the identity \(\lg(n!) = \Theta(n \lg n)\) alongside our ability to manipulate \(\lg(n^n) = n \lg n = \Theta(n \lg n)\). I went so far as to graph the two equations to see that while \(B\) is always larger than \(A\), it grows at an identical rate. Fascinating.