Explore BrainMass

# Definition of small O-notation

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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