Prove it! = O (n ^ n)

Question

How can I prove it n! = O (n ^ n)?

Answer 1

I assume that you want to prove that the function n! is an element of the set O(n^n) . This can be proved quite easily:

Definition: A function f(n) is an element of the set O(g(n)) if there exists c>0 such that m exists such that for all k>m we have f(k)<=c*g(k) .

So we have to compare n! with n^n . Let them write one below the other:

 n! = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1 n^n = n * n * n * n * ... * n * n * n 

As you can see, the first row ( n! ) And the second row ( n^n ) have exactly n elements on the right side. If we compare these elements, we will see that each element is no larger than the corresponding element in the second row. So n! <= n^n n! <= n^n (at least for n> 5).

So, we can - take a look at the definition - say that there exists c=1 such that there exists m=5 such that for all k>5 we have k! < k^k k! < k^k , which proves that n! really an element of O(n^n) .

Answer 2

Note: Below is the answer to the original Question, which was: "Prove that n! = N ^ n"

I can prove that this is not so easy: take n = 5.

 n! = 120 n^n = 3125 

Answer 3

It is not true that n! = N ^ n, and therefore you cannot prove it. Also, the solution to your recursive relationship is not n! or n ^ n. (It satisfies T (1) = 1 * 1 + 1 = 2, which is neither 1 nor 1 ^ 1.)

What exactly are you trying to do and why?

Answer 4

for n==2 , n! = 2 != 4 = n^n n! = 2 != 4 = n^n .
for n!=2 , (n-1) divides n! but n-1 does not divide n^n ( n^n mod n-1 == 1 )

Actual mixing approaching n! ~ sqrt(2 Pi n) (n/e)^n n! ~ sqrt(2 Pi n) (n/e)^n

What is your math background? Do you need comprehensive analytical evidence or something more combinatorial in nature?

Answer 5

n! != n^n n! != n^n . However, the sequence T(n) defined above is not n! . But is it equal to n^n ? For n=1 , T(1) = 1*T(0) + 1 = 1*1 + 1 = 2 , but n^n = 1^1 = 1 . However, assuming that you also meant T(1) = 1 , then they are equal for n=1 . Following further, for n=2 , then T(2) = 2*T(1) + 1 = 2*1 + 1 = 3 ! = 2^2 . So I'm honestly not sure what you are trying to ask.