# Definition of small O-notation

See the attach file for problem. Please read R as R+

Question :

Prove that ! ( )

n

n ∈ο n by using the definition of the small o- notation.

Definition: Let : N →R∪{0}, where

∫

N is the set of all non-negative integers:

R is the set of all positive real numbers.

f

0 0

o( f )={ g : N →R ∪{0}|∀c∈R,∃n ∈N :g(n) <cf (n),∀n ≥n }

Solution

The factorial of n, represented by n! is defined for integers n ≥ 0 as

n! = 1 if n=0

= n. (n-1)! if n>0

First of all let us try and arrive at an intuitive solution. A weak upper bound on n! is n

n

, since

each of the n terms in the factorial product is at most n. The o-notation is used to denote an upper

bound that is NOT asymptotically tight.

Hence, intuitively ! ( )

n

n ∈ο n

Proof:

To prove this we need to prove that the definition of o-notation holds.

According to the definition of o-notation, we need to prove that for any positive constant c > 0,

there exists a constant n0 >0 such that

0 ≤ n! < c n

n

for all n ≥ n0 Equation (i)

So it now boils down to showing that the inequalities hold and then we are done.

(a) The first inequality (0 ≤ n!) follows from the definition of n! :

• n! is always greater than 0.

• Minimum value of n! is 1 which occurs when n=0.

Hence n! ≥ 0 for all n ≥ 0.

(b) To show the second inequality, we just need to look at the factorials carefully.

Once again, let us start with the basic factorials: 0! = 1 and 1! = 1. So in order for these factorials

to satisfy the inequality, it is obvious that c must be >1 [because 1 < c*1 iff c >1].

For all other factorials, i.e. n ≥ 2, the inequality will hold for any c > 1. So, in order to

summarize:

The second inequality n! < c n

n

is true for n ≥ 2 for any c ≥1. This is in the same form as

Equation (i).

Therefore for all c ε R+, n0 = 2 satisfies Equation (i).

Hence ! ( )

n

n ∈ο n is proved

#### Solution Summary

Algorithm is featured.