Purchase Solution

# Definition of small O-notation

Not what you're looking for?

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

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

##### Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

##### Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

##### C++ Operators

This quiz tests a student's knowledge about C++ operators.

##### Javscript Basics

Quiz on basics of javascript programming language.

##### Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.