Results 1 to 3 of 3

Math Help - is n^n O(2^n)?

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    9

    is n^n O(2^n)?

    Trying to figure out this problem. But, I think my log abilities are betraying me:

    Determine whether the following is true or false. If true justify your answer by finding constants C and K. If the statement is false, supply a counter example:
    n^n is O(2^n)

    I set n^n <= 2^n
    ln (n^n) <= ln(2^n)
    n ln(n) <= n ln(2)
    n <= ln(2)

    This doesn't seem correct. Any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by othnin View Post
    Trying to figure out this problem. But, I think my log abilities are betraying me:

    Determine whether the following is true or false. If true justify your answer by finding constants C and K. If the statement is false, supply a counter example:
    n^n is O(2^n)

    I set n^n <= 2^n
    ln (n^n) <= ln(2^n)
    n ln(n) <= n ln(2)
    n <= ln(2)

    This doesn't seem correct. Any ideas?
    2^n = O(2^n), 2^n = O(3^n), ... , 2^n = O(n^n). But n^n \neq O(2^n).

    To check if f(n) = O(g(n)) is true (see wiki), you need to check |f(n)| / |g(n)| <= M, M is a positive real number(not infinity), where n goes to a sufficiently large number (this n might go to the infinity so u can use a L'Hospital's rule as well).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    9
    Thanks, I was really off base on that one.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum