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 465 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Shaik Masthan commented Aug 14, 2018 reply Follow Share simply apply log both sides 0 votes 0 votes Bhagyashree Mukherje commented Aug 14, 2018 reply Follow Share Can you please provide the steps? I am unable to get it 0 votes 0 votes Shaik Masthan commented Aug 14, 2018 reply Follow Share LOG( (log n)3 ) ===> 3 log ( log n ) --- f(n) LOG ( $n^{\frac{1}{3}}$) ===> $\frac{1}{3}$ log ( n ) ---- g(n) f(n) = O(g(n)) 3 votes 3 votes Bhagyashree Mukherje commented Aug 14, 2018 reply Follow Share Got it.Thank you 0 votes 0 votes pankaj_vir commented Aug 14, 2018 reply Follow Share ${log}^3n = logloglogn$ on taking $log$, we get ${log}^3n = loglogloglogn$ and $n^{\frac{1}{3}} = \dfrac{1}{3}log n$ take large values of n ( in power of two ) and compare both the values 0 votes 0 votes Bhagyashree Mukherje commented Aug 14, 2018 reply Follow Share Isn't it (log n)^3 instead of logloglogn? 0 votes 0 votes Shaik Masthan commented Aug 14, 2018 reply Follow Share https://gateoverflow.in/229833/self-doubt-algorithms 1 votes 1 votes pankaj_vir commented Aug 14, 2018 reply Follow Share @Bhagyashree Mukherje ; I don't think so 0 votes 0 votes 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.