next up previous
Next: H.W.1 Up: GROWTH RATES AND ASYMPTOTIC Previous: AND OTHER NOTATIONS

$\sqrt(n)$ VERSUS $\log_{2}^{3}n$

show $\sqrt{n} = \Omega (\log_{2}^{3} n)$

$\Rightarrow \ln^3 n = O(\sqrt{n} ) $

$\frac{\ln^{3} n}{\sqrt{n}}=\lim_{n \rightarrow \infty}
\frac{3\log^{2} n 1/n}{1/2 n^{-1/2}}$

$=\lim_{n \rightarrow \infty} 6 \frac{\log^{2} n}{\sqrt{n}}=\lim_{n \rightarrow \infty} 6\frac{2\log n 1/n}{1/2n^{-1/2}}$

$=\lim_{n \rightarrow \infty} 24\frac{\log n}{\sqrt{n}}=\lim_{n \rightarrow \infty} 24\frac{1/n}{1/2 n^{-1/2}}$

$=\lim_{n \rightarrow \infty} \frac {48}{\sqrt{n} } \rightarrow 0$

$\Rightarrow \log^{3} n=O(\sqrt{n})$



Sushil_Prasad 2010-06-21