Design and

Analysis of
Algorithm
Types of Function
Value Name
1 Constant
logn Logrithemic
n Linear
n2 Quadratic
n3 Cubic
2n Exponential
n! Factorial
nn Power
 Growth Rates Compared
n= n= n= n=8 n=16 n=32
1 2 4
1 1 1 1 1 1 1
logn 0 1 2 3 4 5
n 1 2 4 8 16 32
nlog 0 2 8 24 64 160
n
n2 1 4 16 64 256 1024
n3 1 8 64 512 4096 32768
2n 2 4 16 256 65536 4294967
296
n! 1 2 24 40320 20922789 2.631 x
888000 1035
n
 Asymptotic Analysis
Objectives
The purpose of asymptotic analysis is to examine the behavior of an
algorithm for large input size. More specifically, if T(n) is the
running time for an input of size n , we would want to know the
behavior or growth rate of T(n) for very large values of n. An
analysis of algorithm for large input is referred to as asymptotic
analysis.

The asymptotic behavior of an algorithm is often compared to

some standard mathematical function, such as n2, n lg n etc The
relationship or similarity of behavior is often expressed by a
special notation which is called asymptotic notation.

The standard asymptotic notations commonly used in the analysis of

algorithms are known as O (Big Oh), Ω (Big Omega), and θ(Theta).
Asymptotic Notations
O (big-oh) Upper Bound
Ω (big-omega) Lower Bound
Θ (theta) Tight Bound
 O (big-oh) Upper Bound
f(n)= O(g(n)) iff there exist two positive
constants c and n0 such that
f(n) <= cg(n) for all n >= n0

g(n)

f(n)
Tt

1 n0 n
O (big-oh) Upper
Bound 1
Suppose
logn
f(n) = 4n+1
n
f(n) <= c g(n)
nlogn
4n+1 <= c n
n2

4n+1 <= 5 n ( n>0) n3

2n
4n+1 <=n!
nn
 O (big-oh) Upper
Bound Examples
Example(1): 3n2 + 5n+ 20 = O(n2)

lim 3n2 + 5n + 20
n→∞ n2

=3+ 5 / n +20 / n2

= 3+0+0 =3 ( positive constant)

Therefore, 3n2 + 5n+ 20 = O(n2)

Example(2): 10n2 + 25n+ 7 = O(n3)

lim 10n2 + 25n + 7

n→∞
n3
=10 / n+ 25 / n2 + 7 / n3

=0+0+0 = 0

Therefore, 10n2 + 25n+ 7 = O(n3)

Ω (big-omega) Lower Bound
f(n)= (g(n)), iff there exit positive
constants c and n0 such that
f(n) >= cg(n) for all n >= n0

f(n)

g(n)

n0 n
Ω (big-omega) Lower
Bound 1
Suppose
logn
f(n) = 4n+5 4n+5
>= n
f(n) >= c g(n)
4n+5 >= c n nlogn
n2

4n+5 >= 4 n (for all n) n3

2n
n!
nn
 Ω (big-omega) Lower
Bound
Example(1): 7n2 + 12n+8= Ω(n2)

lim 7n2 + 14n + 8

n→∞
n2

= 7+ 14 / n +8 / n2
=7+0+0
=7
(Non-zero constant)
Therefore, 7n2 + 14n+ 8 = Ω(n2)
Example(2): 10n3 + 5n+ 2 = Ω(n2)

lim 10n3 + 5n + 2
n→∞ 2 n

=10 n+ 5 / n + 2 / n2
=∞+0+0
=∞
Therefore, 10n3 + 5n+ 2 = Ω
(n2)
Θ (theta) Tight Bound
f(n)= (g(n)), iff there exit positive
constants c1 and c2 and n0 such that
c1 g(n) <= f(n) <= c2g(n)
for all n >= n0
c2g(n)

f(n)

c1g(n)

n0 n
Θ (theta) Tight Bound
Suppose
f(n) = 4n+1
c1 g(n) <= f(n) <= c2 g(n)
c1 n <= 4n +1<= c2 n

4n <= 4n+1 <= 5n (n>0)

 Θ (theta) Tight Bound
Examples
Example(1): 45n3 - 3n2 - 5n+ 20 = θ(n3)
lim 45n3 -3n2 - 5n + 20
n→∞ 3 n

= 45-3 / n -5 / n2 +20/n3
= 45 - 0 – 0 + 0
=45 (non-zero
Therefore, 45n3 -constant)
3n2 - 5n+ 20 = θ(n3)

Example(2): n lg n + n + n2 = θ(n2)

lim n lg n + n + n2
n→∞ n2
= lg n / n +1/n +1
= 0 +0 + 1
=1
(non-zero constant)
 Θ (theta) Tight Bound
Examples
Example(3): 45n3 - 3n2 - 5n+ 20 ≠ θ(n4)
lim 45n3 -3n2 - 5n + 20
n→∞ 4 n

= 45 / n - 3 / n2 - 5 / n3 + 20 / n4
=0-0-0+0
= 0 (zero is excluded from the permissible range for Ө-
Therefore, 45n3 -notation)
3n2 - 5n+ 20 ≠
θ(n3)

Example(4): n lg n + n ≠ θ(n2)
lim n lg n + n
n→∞
n2
= lg n / n + 1/n ( Using the L’Hopital Rule to evaluate the limit of lgn /n)
= 0 +0
=0
Thus, n lg n + n ≠ θ(n2)
 Asymptotic
Notation
Constant Running Time
If running time T(n)=c is a constant, i. e independent of
input size, then by convention, the asymptotic behavior is
denoted by the notation
O(c) = O(1) , θ (c) = θ(1), Ω(c) = Ω(1)
The convention implies that the running time of an
algorithm ,which does not depend on the size of input,
can be expressed in any of the above ways.

 If c is constant then using basic definition it can be

shown that
O( c.f(n) ) = O( f(n) )
θ( c.f(n) ) = θ( f(n) )
Ω( c.f(n) ) = Ω( f(n ))
 Asymptotic
Notation
Constant Running Time

Example: (i) O(1000n) = O(n),

(ii) θ(7lgn ) = θ (lg n),
(iii) Ω(100 n!) = Ω(n!)
The above results imply that in asymptotic
notation the multiplier constants in an expression
for the running time can be dropped
 Asymptotic
Notations
Relationships
Theorem: If f(n) = θ( g(n) ) then

f(n) = Ω( g(n) ), and O( g(n) )

f(n)=

and f(n) = O( g(n) )

Conversely, if f(n) = Ω( g(n) )

then f(n) = θ( g(n) )

 Asymptotic
Notations
Relationships
The above relations can be established by using
basic definitions

Example(1): Since, n(n-1)/2 = θ(n2 ), therefore it

follows that
n(n-1)/2 = Ω(n2 )
n(n-1)/2 = O(n2 )
Example(2): It can be shown that
5n2+1 = Ω(n2 )
and 5n2+1 = O(n2 )
Therefore, 5n2 + 1 = θ(n2 )
 Asymptotic Set
Notations Relationship
We have seen that if f(n) = O( g(n) ) and f(n) = Ω(g(n)) then f(n)
= Ө( g(n) )

Using set notation we can express the relationship as

follows: if f(n) O( g(n) ),
and f(n) Ω (g(n)),
then f(n)  Ө( g(n) ) ,
where Ө(g(n)) = O( g(n) ) ∩ Ω (g(n) )

The above property is illustrated by the following Venn

diagram

O(g(n)) Ө(g(n)) Ω(g(n))

 Asymptotic Set
Notation Example
The relationship among the O ,Ω , and θ notations can
be expressed using set notation Consider, for example,
the following sets of growth functions
O(n2) = {√n, n+5, lg n+4n, n1.5+n, √n+5n2, n2+5n, lg n+4n2, n1.5+3n2 }

Ω(n2) = { √n+5n2, n2+5n, lg n+4n2, n1.5+3n2 , 5n2+n3, n3 +n2+n, lg n+4n4 }

θ(n2) = { √n+5n2 , n2+5n, lg n+4n2, n1.5+3n2 }

 It follows that θ(n2) = O(n2) ∩ Ω(n2)

 Asymptotic Set
Notation Example
The following Venn diagram represents the preceding set
relations

√n √n+5n2 √n+5n2 5n2+n3

n+5 n2+5n n2+5n n3 +n2+n
lg n+4n2
lg n+4n 1.5 lg n+4n2 lg n+4n4
n +3n2
n1.5+3n2 nlg n+3n4
n1.5+n

O(n2) Ω(n2)

√n √n+5n2 5n2+n3
n+5 n2+5n n3 +n2+n
lg n+4n lg n+4n lg n+4n4
2

n1.5+3n2 nlg n+3n4

n1.5+n

θ(n2)
 Asymptotic
Notation
Order Theorem
Theorem: If f1(n) = O( g1(n) ) and f2(n) = O( g2(n) ) then

f1(n) + f2(n)= O( max( g1(n) , g2(n) )

Theorem: If f1(n)= O(g1(n)) , f2(n) =O(g2(n)), f3(n)=O(g3(n))…., fk(n)=O(gk(n)) then

f1(n) + f2(n) + f3(n) ….+ fk(n) = O( max (g1 (n), g2 (n), g3 (n)…, gk(n) ) )

where max means fastest growing function