Proving log(n)^3 = O(n^(1/3)) using Big O notation

  • Thread starter Thread starter hosman
  • Start date Start date
AI Thread Summary
The discussion revolves around proving that log(n)^3 = O(n^(1/3)). The initial approach involved using derivatives to compare the growth rates of log(n) and n^(1/9), concluding that log(n) grows slower than n^(1/9) for large n. However, it was later clarified that the original problem is actually asking for a proof that log(n)^3 is o(n^(1/3)), indicating a stricter condition than big O notation. This distinction highlights the need for a more precise analysis of the growth rates. The conversation emphasizes the importance of correctly interpreting the notation in complexity analysis.
hosman
Messages
2
Reaction score
0
is log(n)^3 O(n^(1/3))??

Homework Statement



So the problem has to do with big o notation, I came up with a solution but I think even in this summed up solution I give I am making too much assumptions or that it is just plainly wrong, if it is please let me know.

Homework Equations



So the original question is stated as follows:

Q:Show that \log{n}^{3}=O(n^{1/3})

The Attempt at a Solution



My basic idea was to use the derivative of the third root of both functions and prove that n^{1/9} will have the greater one of the two and thus at some point the two functions will be equal and then n^{1/9} will become greater allowing \log{n} to have a order complexity of n^{1/9},
which implies \log{n}^{3}=O(n^{1/3})

so here it is:
if n^{1/3} has O(n^{1/3}) the so should...
\sqrt[3]{n^{1/3}} have O\left(\sqrt[3]{n^{1/3}}\right)
and so I take the derivative of the third root (to simplify problem) of these functions and get:

\frac{d}{dn}\left(\log{n}\right)=\frac{1}{n\ln{10}}

\frac{d}{dn}\left(n^{1/9}\right)=\frac{1}{9n^{8/9}}

clearly \frac{1}{n}<\frac{1}{n^{8/9}} for big values of n.

thus the derivative of n^{1/9} will eventually become greater than \log{n}} and this means (leaving out the actual calculation of following constants):

\exists N,c\in\Re such that \forall n \geq N

\log{n} \leq c\left(n^{1/9}\right) so that (skipping some more steps..)

\log{n}^{3}=O(n^{1/3})

for the sake of brevity I am leaving out steps but I think that the solution still makes sense?
 
Physics news on Phys.org


I just found out that the actual problem is litte o not big O so its
Q: proof (logn)^3 is o(n^(1/3))

hmmmmm...
 
Back
Top