3-2 Relative asymptotic growths
Indicate for each pair of expressions ( A , B ) (A, B) ( A , B ) in the table below, whether A A A is O O O , o o o , Ω \Omega Ω , ω \omega ω , or Θ \Theta Θ of B B B . Assume that k ≥ 1 k \ge 1 k ≥ 1 , ϵ > 0 \epsilon > 0 ϵ > 0 , and c > 1 c > 1 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 Ω ω Θ lg k n n ϵ y e s y e s n o n o n o n k c n y e s y e s n o n o n o n n sin n n o n o n o n o n o 2 n 2 n / 2 n o n o y e s y e s n o n lg c c lg n y e s n o y e s n o y e s lg ( n ! ) lg ( n n ) y e s n o y e s n o y e s
\begin{array}{ccccccc}
A & B & O & o & \Omega & \omega & \Theta \\
\hline
\lg^k n & 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
\end{array}
A lg k n n k n 2 n n l g c lg ( n !) B n ϵ c n n s i n n 2 n /2 c l g n lg ( n n ) O yes yes n o n o yes yes o yes yes n o n o n o n o Ω n o n o n o yes yes yes ω n o n o n o yes n o n o Θ n o n o n o n o yes yes