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

  • Thread starter Thread starter hosman
  • Start date Start date
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 replies · 12K views
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 [tex]\log{n}^{3}=O(n^{1/3})[/tex]

The Attempt at a Solution



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

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

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

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

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

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

[tex]\exists N,c\in\Re[/tex] such that [tex]\forall n \geq N[/tex]

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

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

for the sake of brevity I am leaving out steps but I think that the solution still makes sense?
 
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...