Purchase Solution

Definition of small O-notation

Not what you're looking for?

Ask Custom Question

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

Attachments
Purchase this Solution

Solution Summary

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

Purchase this Solution


Free BrainMass Quizzes
Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

C# variables and classes

This quiz contains questions about C# classes and variables.

Javscript Basics

Quiz on basics of javascript programming language.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.