0 votes 0 votes Show that $log^{3}n$ is $o\left ( n^{1/3} \right )$ Algorithms algorithms time-complexity + – srestha asked Aug 14, 2018 srestha 492 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Bhagyashree Mukherje commented Aug 14, 2018 reply Follow Share Please refer the above mentioned link for clarification 0 votes 0 votes ankitgupta.1729 commented Aug 15, 2018 reply Follow Share It can also be proved by formal definition of o-notation i.e. g(n) $\in$ f(n) if $\lim_{n \rightarrow \infty } \frac{f(n)}{g(n)} = \infty$ So, here we have to prove , $\lim_{n \rightarrow \infty } \frac{n^{\frac{1}{3}}}{(logn)^{3}} = \infty$ i.e. growth rate of n1/3 is much higher than (logn)3 So, here , $\lim_{n \rightarrow \infty } \frac{n^{\frac{1}{3}}}{(logn)^{3}}$ Now , apply L'Hopital's Rule , $\lim_{n \rightarrow \infty } \frac{(\frac{1}{3})n^{\frac{1}{3}}}{3(logn)^{2}}$ Again , Apply L'Hopital's Rule , $\lim_{n \rightarrow \infty } \frac{(\frac{1}{9})n^{\frac{1}{3}}}{6(logn)}$ Again , Apply L'Hopital's Rule , $\lim_{n \rightarrow \infty } \frac{(\frac{1}{27})n^{\frac{1}{3}}}{6}$ So, $\lim_{n \rightarrow \infty } \frac{(\frac{1}{27})n^{\frac{1}{3}}}{6}$ = $\infty$ So, Now we can say that :- g(n) $\in$ f(n) i.e. (logn)3 $\in$ o(n1/3) 1 votes 1 votes srestha commented Aug 15, 2018 reply Follow Share thanks 1 votes 1 votes Please log in or register to add a comment.