Problem 3.2

Relative asymptotic growths

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. Your answer should be in the form of the table with "yes" or "no" written in each box.

A B $O$ $o$ $\Omega$ $\omega$ $\Theta$
$\lg^kn$ $n^\epsilon$ yes yes no no no
$n^k$ $c^n$ yes yes no no no
$\sqrt{n}$ $n^{\sin{n}}$ no no no no no
$2^n$ $2^{n/2}$ no no yes yes no
$n^{\lg{c}}$ $c^{\lg{n}}$ yes no yes no yes
$\lg(n!)$ $\lg(n^n)$ yes no yes no yes