Skip to content

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