Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By mdm508

Thread: is n^0.01 Omega log(n) or BigO(log(n))

  1. #1
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    43
    Thanks
    1

    is n^0.01 Omega log(n) or BigO(log(n))

    I was plugging in huge values for n and noticed n^0.01 grows incredibly slowly, much slower then log(n) it seems. So my initial thought was that $$n^{0.01}~is~BigO(log(n))$$.
    However I came across the rule in my book that,
    $$log^x(n)~is~BigO(n^y)$$ for any fixed constant x > 0 and y > 0,
    which made me think my initial thought was wrong.
    Last edited by mdm508; Jan 11th 2017 at 12:48 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2009
    Posts
    348
    Thanks
    48

    Re: is n^0.01 Omega log(n) or BigO(log(n))

    Consider that n^{0.01} = e^{0.01 ln(n)}

    You can use the Maclaurin series expansion of e^x in order to show that by the Formal Definition of Big O notation, that it's not the case your initial thought was true.
    https://en.wikipedia.org/wiki/Big_O_...mal_definition

    ie. Show that for a constant M, you can choose an n_0 such that for n \geq n_0 , |e^{0.01 ln(n)}| \geq M |ln(n)|
    Last edited by MacstersUndead; Jan 11th 2017 at 05:28 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2015
    From
    san fransisco
    Posts
    43
    Thanks
    1

    Re: is n^0.01 Omega log(n) or BigO(log(n))

    that is an incredibly creative way to solve this. I never in a million years would have thought to go about it this way.
    I ended up just proving that $$lim_{x\to\infty}\frac{n^{0.01}}{\log{n}} = \infty$$
    Last edited by mdm508; Jan 11th 2017 at 05:44 PM.
    Thanks from MacstersUndead
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    348
    Thanks
    48

    Re: is n^0.01 Omega log(n) or BigO(log(n))

    Your method is quicker. Great catch.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Big O and Omega help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 24th 2014, 04:46 PM
  2. Replies: 3
    Last Post: Jul 25th 2011, 09:46 AM
  3. dimensions of omega
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: May 19th 2008, 03:59 AM
  4. Big Oh and Big Omega
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 4th 2008, 12:01 AM
  5. Omega
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jan 20th 2008, 01:09 PM

/mathhelpforum @mathhelpforum