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 >,$ and $c>1$ are constants. Write your answer in the foem of the table with "yes" or "no" written in each box.
A | B | O | o | $\Omega$ | $\omega$ | $\Theta$ |
---|---|---|---|---|---|---|
$\lg^k n$ | $n^{\epsilon}$ | yes | yes | no | no | no |
$n^k$ | $c^n$ | yes | yes | no | no | no |
$\sqrt{n}$ | $c^{\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 |