Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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....
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook