# 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

https://brainmass.com/computer-science/c/definition-small-notation-8631

#### Solution Summary

The definition of small o-notation is examined. The non-negative integers and positive real number functions are given.