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

1. ## 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?

2. Originally Posted by othnin
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).

3. Thanks, I was really off base on that one.