Prove that 2n is 0 n Prove that n is O nn By finding appr

Prove that 2^n is 0 (n ! ). Prove that n ! is O (n^n). By finding appropriate values of c and n_0, prove that: f (n) = 3 n log n + 4 n^2 + 3 n is O(n^2).

Solution

(1)Look at the positive series n=1 to 2^n/n!

Using ratio test,

(2)an+1/an=2n+1(n+1)!/n!2n=2/n+1

As n tends to infinity, 2/n+1 tends to 0.

Thus

(3)The series in (1) converges(3)

(4)an=2^n/n!

So, n tends to infinity, it tends to 0

Thus, for some

NNandn>N

2^n/n!<12^n=O(n!)

Hence Proved.

Q 2:

Definition: A function f(n) is element of the set O(g(n))

if there exists a c>0 such that there exists a m such that for all k>m we have that f(k)<=c*g(k).

So, we have to compare n! against n^n. Let\'s write them one under another:

As you can see, the first line (n!) and the second line (n^n) have both exactly n items on the right side.

If we compare these items, we see that every item is at most as large as it\'s corresponding item in the second line. Thus n! <= n^n (at least for n>5).

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

Q 3:

We can write it as

3n log n + 4n^2 + 3n <=cn^2

Divide whole by n^2,

4 + 3/n + 3logn/n <=c

Lets use log 2.

n0 = 1, c = 7

n0=2, c = 7

n0=3, c = 6.5

At n0 = infinity, c = 4