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