1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is log(n)^3 O(n^(1/3))?

  1. Feb 8, 2009 #1
    is log(n)^3 O(n^(1/3))??

    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations

    So the original question is stated as follows:

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

    3. 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?
     
  2. jcsd
  3. Feb 9, 2009 #2
    Re: is log(n)^3 O(n^(1/3))??

    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....
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook