Subject Name: Design and Analysis of

Algorithms
Module No: 1
Module Name: Introduction
 Outline-Module 1
Sr. No Topic
Performance analysis , space and time complexity Mathematical background for
1
algorithm analysis
2 Growth of function – Big –Oh ,Omega, Theta notation

3 Analysis of Selection Sort

4 Analysis of Insertion Sort

5 The substitution method and Recursion tree method

6 Master Theorem

2 Module 1- Introduction
Module 1 : Introduction

Lecture No: 4
Analysis of Insertion Sort
Insertion Sort

Idea:
Like sorting a hand of playing cards
Start with an empty left hand and the cards facing down on the table.
Remove one card at a time from the table, and insert it into the correct
position in the left hand.
Compare it with each of the cards already in the hand, from right to left
The cards held in the left hand are sorted these cards were originally the
top cards of the pile on the table

4 Module 1- Introduction
Insertion Sort

To insert 12, we need to make room

for it by moving first 36 and then 24.

5 Module 1- Introduction
Insertion Sort

6 Module 1- Introduction
Insertion Sort

7 Module 1- Introduction
Insertion Sort

input array

5 2 4 6 1 3

at each iteration, the array is divided in two sub-arrays:

left sub-array right sub-array

sorted unsorted

8 Module 1- Introduction
Insertion Sort

9 Module 1- Introduction
INSERTION-SORT
Algorithm INSERTION-SORT(A)
{//problem description: This algorithm sort the element using Insertion sort
//Input: an array of element a[0,1…n-1] that is to be stored
//output: the sorted array A[0,1,….n-1] 1 2 3 4 5 6 7 8
for j ← 2 to n
do key ← A[ j ] a1 a2 a3 a4 a5 a6 a7 a8
// Insert A[ j ] into the sorted sequence A[1 . . j -1]
i←j-1 key
while i > 0 and A[i] > key
do A[i + 1] ← A[i]
i←i– 1
A[i + 1] ← key
}
Insertion sort – sorts the elements in place

10 Module 1- Introduction
 Analysis of Insertion Sort
cost times
INSERTION-SORT(A)
c1 n
for j ← 2 to n
c2 n-1
do key ← A[ j ]
c3 n-1
i←j-1
c4 
n
tj
while i > 0 and A[i] > key j 2

c5 
n
(t j  1)
do A[i + 1] ← A[i] j2

i←i– 1

n
c6 j2
(t j  1)
A[i + 1] ← key
c7 n-1
T (n)  c1n  c2 (n 1)  c3 (n 1)  c4  t j  c5  t j 1 c6  t j 1 c7 (n 1)
n n n

j 2 j 2 j 2

11 Module 1- Introduction
Analysis of Insertion Sort

Step 1: the Input size is n

Step 2: Basic Operation : while i > 0 and A[i] > key
Step 3:Basic operation complexity depends on input and worst case

 
n j 1
c(n)= j 2 i0
1

Step 4: Calculation of complexity

 
n j 1
c(n)= 1
j 2 i0

=

n
j 2
j
= (n-1)(n)/2
=O(n²)

12 Module 1- Introduction
Module No 1: Introduction

Lecture No: 5
The substitution method and
Recursion tree method
Recurrence relation

What is Recurrence?
T(n) = T(n-1) + 1

A recurrence relation is an equation that defines a sequence based on a rule

that gives the next term as a function of the previous term(s). It is also defined
as a function by means of an expression that includes one or more smaller
instances of itself.
Example for the recursive definition is factorial function , Fibonacci series.

14 Module 1- Introduction
 Example of Recursive Program

Recursive program to compute n!

n!= { 1
n x (n-1)!
if n=0 or n=1
n>1
T(1) = 1
Factorial(int n) T(2) = T(1) + 1 = 2
T(3) = T(2) + 1 = 3
{ if(n==0 || n==1) .
return 1; .
.
else T(n) = T(n-1) + 1
return n* Factorial(n-1)
}

T(n)= { 1
T(n-1)+1
if n=0 or n=1
n>1

15 Module 1- Introduction
16 Module 1- Introduction
Finding Complexity of recursive algorithms

Recursive Algorithm

Recursion-Tree
Substitution Method Master Method
Method

17 Module 1- Introduction
 Solving Recurrence Relations

Special Cases of Geometric Series and Arithmetic series:

1
1xx   2
for |x| < 1
1x

18 Module 1- Introduction
 Activity

What is the Complexity of

Equation?
T(n)=T(n-1)+1
With initial condition T(0)=0

19 Module 1- Introduction
Example

Consider a recurrence relation

T(n)=T(n-1)+1
With initial condition T(0)=0
Let,
T(n)=T(n-1)+1 ------- equation 1
T(n-1)=T(n-2)+1 -------putting this in equation 1 we get
T(n)=T(n-2)+1+1=T(n-2)+2 ------- equation 2
T(n-2)=T(n-3)+1 -------putting this in equation 2 we get
T(n)=T(n-3)+1+2=T(n-3)+3 ------- equation 3
.
. repeat up to k steps
.
T(n)=T(n-k)+k ------- equation k
The base case is reached when n – k = 0  k = n, we then have :
T(n)=T(0)+n
T(n)=0+n=n
T(n)=O(n)

20 Module 1- Introduction
 Activity

What is the Complexity of

Equation?
T(n)=T(n-1)+n
With initial condition T(0)=0

21 Module 1- Introduction
Example

Consider a recurrence relation

T(n)=T(n-1)+n
With initial condition T(0)=0
Let,
T(n)=T(n-1)+n ------- equation 1
T(n-1)=T(n-2)+n-1 -------putting this in equation 1 we get
T(n)=T(n-2)+(n-1)+n ------- equation 2
T(n-2)=T(n-3)+n-2 -------putting this in equation 2 we get
T(n)=T(n-3)+(n-2)+(n-1)+n ------- equation 3
.
. repeat up to k steps
.

T(n)=T(n-k)+……….(n-2)+(n-1)+n ------- equation k

The base case is reached when n – k = 0  k = n, we then have :
T(n)=T(0)+1+2……….+n
T(n)=0+1+2……….+n
T(n)=n(n+1)/2=O(n²)

22 Module 1- Introduction
 Activity

What is the Complexity of

Equation?
T(n)=T(n/2)+1

23 Module 1- Introduction
Example

Consider a recurrence relation

T(n)=T(n/2)+1
If initial condition is not given consider T(1)=1
Let,
T(n)=T(n/2)+1 ------- equation 1
T(n/2)=T(n/4)+1 -------putting this in equation 1 we get
T(n)=T(n/4)+2 ------- equation 2
T(n/4)=T(n/8)+1 -------putting this in equation 2 8we get
T(n)=T(n/8)+3 ------- equation 3
.
. repeat up to k steps
.
T(n)= T(n/2k )+k ------- equation k
The base case is reached when n / 2k = 1  n = 2k  k = log2 n, we then
have:
Put the value of k in general equation
T(n)=T(1)+ log₂ n
T(n)=1+ log₂ n
T(n)=O(log₂ n )

24 Module 1- Introduction
Substitution Method

Merge Sort T(n)= T(n/2) +T(n/2)+ Cn for n>1 and T(1)=1

T(n)=2T(n/2)+n ------- Equation 1

For n=n/2
T(n/2)=2 T((n/2)/2) +(n/2)] -----Put this in Equation 1

T(n)=2 [2 T((n/2)/2) +(n/2)] + n = 4T(n/4)+2 n

T(n)=4T(n/4)+2n ------- Equation 2

For n=n/4
T(n/4)=2 T((n/4)/2)+(n/4) ---------Put this in Equation 2

T(n)=4 [2 T((n/4)/2)+(n/4)] +2n = 8T(n/8)+ 3n

T(n)=8T(n/8)+3n ------- Equation 3

General Equation at n=k T(n)=2kT(n/2k)+kn

25 Module 1- Introduction
Substitution Method

General Equation at n=k T(n)=2kT(n/2k)+kn

The base case is reached when n / 2k = 1  n = 2k  k = log2 n, we then

have:

T(n)=2kT(n/2k)+kn => T(n)=nT(1)+ log₂ n * n => T(n)=n+ log₂ n * n

Complexity = O(nlog₂ n)

26 Module 1- Introduction
 Activity

What is the Complexity of

Equation?
T(n)=T(n-1)+n4

27 Module 1- Introduction
Example

Consider a recurrence relation

T(n)=T(n-1)+n4

T(n)=T(n-1)+n4 ------- equation 1

T(n-1)=T(n-2)+ (n-1) 4 -------putting this in equation 1 we get
T(n)= T(n-2)+ (n-1)4+ n4 ------- equation 2
T(n-2)=T(n-3)+ (n-2) 4 -------putting this in equation 2 we get
T(n)= T(n-3)+ (n-2)4+ (n-1)4+ n4 ------- equation 3
and in general you'll have
T(n)=T(n−k)+(n−k+1)4+(n−k+2)4+⋯+(n−1)4+n4
= 14 + 24+34 +…….(n-2)4+ (n-1)4+ n4 Initial condition T(0)=0

= n5/5
= O(n5)

28 Module 1- Introduction
 Activity

What is the Complexity of

Equation?
T(n)=4T(n/3)+n2

29 Module 1- Introduction
Example

Consider a recurrence relation

T(n)=4T(n/3)+n2
If initial condition is not given consider T(1)=1
T(n)= 4T(n/3)+n2 ------- equation 1
T(n/3)=4T(n/ 32 )+ (n/3)2 -------putting this in equation 1 we get
T(n)= 4[4T(n/ 32 )+ (n/3)2 ]+n2
= 42 T(n/ 32 )+ 4 (n/3)2 + n2 ------- equation 2
T(n/ 32 )=4T(n/ 33 )+ (n/ 32 )2 -------putting this in equation 2 we get
T(n)= 42 [4T(n/ 33 )+ (n/ 32 )2 ]+ (n/3)2 + n2
= 43 T(n/ 33 )+ 42 (n/ 32 )2+4 (n/3)2 + n2 ------ equation 3
T(n/ 3k )= 4k-1 T(n/ 3k )+ (n/ 3k)2 -------putting this in equation k we get
T(n)= 4k T(n/ 3k )+ 4k-1 (n/ 3k-1)2 … … . + 42 (n/ 32 )2+4 (n/3)2 + n2 ------ equation k
= 4k T(n/ 3k )+ n2 [4k-1 (1/ 3k-1)2 ……. + 42 (1/ 32 )2+4 (1/3)2 + 12]

Constant C
= 4k T(n/ 3k )+ Cn2
T(1)=1 is compare the term T(n/3k)=S(1)
n/3k=1 => n=3k => then k= log3 n
= 4log n T(1)+ Cn2 = nlog 4 + Cn2 = n1.26 + Cn2 =O(n2 )
3 3

30 Module 1- Introduction
 Activity

What is the Complexity of

Equation?
T(n)=2T(n/2+17)+n

31 Module 1- Introduction
Example

Consider a recurrence relation

T(n)=2T(n/2 +17)+n
If initial condition is not given consider T(1)=1
Let,
T(n)=2T(n/2 +17)+n ------- equation 1
T(n/2 +17)=2T((n/2 +17)/2 +17)+(n/2 +17)
=2T(n/4 +25.5) +n/2 +17 -------putting this in equation 1 we get
T(n)=2[2T(n/4 +25.5) +n/2 +17 ]+n
= 22 T(n/4 +25.5)+3n+34 ------- equation 2
T(n/4 +25.5)=2T((n/4 +25.5)/2 +17)+(n/2 +25.5)
= 2T(n/8+29.75)+ n/2 +25.5 -------putting this in equation 2 we get
T(n)= 2 [2T(n/8+29.75)+ n/2 +25.5 ]+3n+34
2

= 23 T(n/8+29.75)+5n+136 ------ equation 3

T(n)= 2 T(n/2 +c1)+(2k+1)n+c2
k k ------- equation k

T(1)=1 is compare the term T(n/2k)=T(1)

If we compare the term T(n/2k)=T(1)
n/2k=1 => n=2k => then k= log₂ n
Put the value of k in general equation
T(n)= nT(1)+(2log₂ n +1)n+c2 T(n)=2n+ 2nlog₂ n+c2
T(n)=O(nlog₂ n )

32 Module 1- Introduction
 Activity

What is the Complexity of

Equation?
T(n)=2T(√n/2)+log₂ n

33 Module 1- Introduction
Example

T(n)=2T(√n/2)+log₂ n
Let, m=log₂ n  n= 2m
T(2m )=2T(2m/2 )+m ------- equation 1
Let, T(2m)=S(m)
S(m)=2 S(m/2) -------putting this in equation 1 we get ------- equation 2
S(m/2)=2 S(m/4)+m/2
S(m)=2[2 S(m/4)+m/2 ] + m -------putting this in equation 2 we get
S(m) = 22 S(m/ 22 ) + 2m ------- equation 3
S(m/4)=2S(m/8)+m/4 -------putting this in equation 2 we get
S(m) = 22 [2 S(m/8)+m/4 ] +2 m
S(m)= 23 S(m/ 23 ) + 3m ------- equation 3
S(m)= 2k S(m/2k )+km ------- equation k
S(1)=1 is compare the term S(m/2k)=S(1)
m/2k=1 => m=2k => then k= log₂ m
Put the value of k in general equation
S(m)= mS(1)+mlog₂ m = m+mlog₂ m now replace S(m) with T(2m)
T(2m)= m+mlog₂ m now replace m=log₂ n and 2m = n
T(n)= log₂n+ log₂n * log₂log₂n = O(log₂n * log₂log₂n )

34 Module 1- Introduction
Recurrence Relations to Remember

Recurrence Algorithm Big-Oh Solution

T(n) = T(n/2) + O(1) Binary Search O(log n)

T(n) = T(n-1) + O(1) Sequential Search O(n)

T(n) = 2 T(n/2) + O(1) tree traversal O(n)

T(n) = T(n-1) + O(n) Selection Sort (other n2 sorts) O(n2)

T(n) = 2 T(n/2) + O(n) Mergesort (average case Quicksort) O(n log n)

35 Module 1- Introduction
 Solving Recurrence Relations

Special Cases of Geometric Series and Arithmetic series:

1
1xx   2 for |x| < 1

1x

1 Module 1- Introduction
The recursion-tree method

 Recursion Tree is another method for solving the recurrence relations.

 A recursion tree is a tree where each node represents the cost of a certain
recursive sub-problem i.e. Cost incurred at various levels of recursion.

 We sum up the values in each node to get the cost of the entire algorithm.
 Generally, used to “guess” a solution for the recurrence

 Convert the recurrence into a tree:

 Each node represents the cost incurred at various levels of recursion

 Sum up the costs of all levels

2 Module 1- Introduction
The recursion-tree method- Example 1

Q. Solve the following recurrence relation using recursion tree method.

T(n) = 2T(n/2) + n
Solution-
Step-01:
Draw a recursion tree based on the given recurrence relation.
The given recurrence relation shows-
-A problem of size n will get divided into 2 sub-problems of size n/2.
-Then, each sub-problem of size n/2 will get divided into 2 sub-problems of size n/4 and
so on.
-At the bottom most layer, the size of sub-problems will reduce to 1.

This is illustrated through following recursion tree-

2 Module 1- Introduction
The recursion-tree method- Example 1

2 Module 1- Introduction
The recursion-tree method- Example 1

2 Module 1- Introduction
The recursion-tree method- Example 1

2 Module 1- Introduction
 Example 1

Solve T(n) = 2T(n/2) + O(n)

T(n) Cn

T(n/2) T(n/2) C(n/2) C(n/2)

T(n/22) T(n/22) T(n/22) T(n/22) C(n/22) C(n/22) C(n/22) C(n/22)

(1)

11 Module 1- Introduction
 Example 1

Solve T(n) = 2T(n/2) + O(n)

Cn
n
C(n/2) C(n/2) n
C(n/22) C(n/22) C(n/22) C(n/22) n
• Cost =n * depth
• At (1)=T(n/2i) n/2i=1
• i=log2 n
• Cost= n log2 n= O(n log2 n)

12 Module 1- Introduction
The recursion-tree method- Example 2

2 Module 1- Introduction
The recursion-tree method- Example 2

2 Module 1- Introduction
The recursion-tree method- Example 2

2 Module 1- Introduction
 The recursion-tree method- Example 2

Solve T(n) = 3T(n/4) +  (n2):

6 Module 1- Introduction
The recursion-tree method- Example 2

2 Module 1- Introduction
 Example 2

Solve T(n) = 3T(n/4) +  (n2): Cost Calculation

Cn2 Cn2

C(n/4)2 C(n/4)2 C(n/4)2 3C(n/4)2

C(n/16)2 C(n/16)2 C(n/16)2 C(n/16)2 C(n/16)2

32C(n/42)2
C(n/16)2 C(n/16)2 C(n/16)2

…
C(n/16)2 n
ith node ∑ 3iC(n/4i)2
i=1

4 Module 1- Introduction
 Example 2

Solve T(n) = 3T(n/4) +  (n2):

Depth Calculation Using Formula

1
ith node
n
∑ 3iC(n/4i)2 1xx   2 for |x| < 1
i=1
1x
n
= 2
=Cn ∑ (3/16)i • At  (1)=T(n/4i) n/4i=1 i=log4 n
i=1
• So tree has i=log4 n+1 levels
=Cn2(1/(1-(3/16)))
• No of nodes at depth i => 3i => 3log4n=> nlog43
=
=16/13 Cn2

  (n2)

5 Module 1- Introduction
 Example 3

Solve T(n) = T(n/4) + T(n/2) + n2:

T(n) n2

T(n/4) T(n/2) (n/4)2 (n/2)2

T(n/16) T(n/8) T(n/8) T(n/4) (n/16)2 (n/8)2 (n/8)2 C(n/4)2

(1)

7 Module 1- Introduction
 Example 3

Solve T(n) = T(n/4) + T(n/2) + n2:

n2
n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 n 2
256

…
(1)

geometric series
Total =
n
= (n2)
2

1  16  16
5 5     
2 5 3
16

8 Module 1- Introduction
 Example 4

Solve T(n) = T(n/3) + T(2n/3) +O(n)

T(n) Cn

T(n/3) T(2n/3) C(n/3) C(2n/3)

T(n/32) T(2n/32) T(2n/32) T(22n/32) C(n/32) C(2n/32) C(2n/32) C(22n/32)

(1)

9 Module 1- Introduction
 Example 4

Solve T(n) = T(n/3) + T(2n/3) +O(n)

Cn n
C(n/3) C(2n/3) n
C(n/32) C(2n/32) C(2n/32) C(22n/32) n
• Cost =n * depth
• At (1)=T(n(2/3)i) n(2/3)i=1 n=(3/2)i
• i=log3/2 n
• Cost= n log3/2 n = O(n log3/2 n)

10 Module 1- Introduction
 Example 5

Solve T(n) = 2T(n/2) + 4n

T(n) 4n

T(n/2) T(n/2) 4(n/2) 4(n/2)

T(n/22) T(n/22) T(n/22) T(n/22) 4(n/22) 4(n/22) 4(n/22) 4(n/22)

(1)

13 Module 1- Introduction
 Example 5

Solve T(n) = 2T(n/2) + 4n

4n
4n

4(n/2) 4(n/2) 4n

4(n/22) 4(n/22) 4(n/22) 4(n/22) 4n

• Cost =4n * depth
• At (1)=T(n/2i) n/2i=1
• i=log2 n
• Cost= 4n log2 n=O(n log2 n)

14 Module 1- Introduction
 Example 6

Solve T(n) = 2T(n/2) + n2

T(n) n2

T(n/2) T(n/2) (n/2)2 (n/2) 2

T(n/22) T(n/22) T(n/22) T(n/22) (n/22) 2 (n/22) 2 (n/22) 2 (n/22) 2

(1)

15 Module 1- Introduction
 Example 6

Solve T(n) = 2T(n/2) + 4n

n2 n2

(n/2) 2 (n/2) 2 n2/2

(n/22) 2 (n/22) 2 (n/22) 2 (n/22) 2 n2/4

• Cost =n2 * ( 1 + 1/2 + 1/22 + 1/23 +…… 1/2n)

• Cost =n2 (1 / (1-1/2)) =2 n2
=O(n2)

16 Module 1- Introduction
Module 1- Introduction

Lecture No: 6 Master Theorem

Master Method (cont..)
 In the standard recurrence relation each term has some significance,

T(n)=a T(n/b) + f(n)

where,
• n is the size of the problem.
• a is the number of sub problems in the recursion.
• n/b is the size of each sub problem. (Here it is assumed that all sub
problems are essentially the same size.)
• f (n) is the sum of the work done outside the recursive calls, which
includes the sum of dividing the problem and the sum of combining
the solutions to the sub problems.
• It is not possible always bound the function according to the
requirement, so we make three cases which will tell us what kind of
bound we can apply on the function.

60 Module 1- Introduction
 The Master theorem
 Let a ≥ 1 and b > 1 be constants, let f(n) be a function and let T(n) be
defined on the non negative integers by the recurrence.

 Then T(n) has the following asymptotic bounds,

1. If f(n) = O(n log b a - ᵋ ) for some constant Є >0 , then T(n) = Ө(n log b a )

2. If f(n) = Ө(n log b a ), then T(n) = Ө(n log b a log n)

3. If f(n) = Ω(n log b a + ᵋ ) for some constant Є >0 and if a f(n/b) ≤ c f(n)
for some constant c<1 and all sufficient large n, then T(n) = Ө(f(n))

61 Module 1- Introduction
The Master theorem(cont..)
Each of the conditions can be interpreted as:

• If the cost of solving the sub-problems at each level increases by a

certain factor, the value of f(n) will become polynomial smaller than n log
a . Thus, the time complexity is oppressed by the cost of the last level
b
i.e. n log b a

• If the cost of solving the sub-problem at each level is nearly equal, then
the value of f(n) will be n log b a . Thus, the time complexity will be f(n)
times the total number of levels ie. n log b a * log n

• If the cost of solving the sub problems at each level decreases by a

certain factor, the value of f(n) will become polynomially larger than
n log b a . Thus, the time complexity is oppressed by the cost of f(n).

62 Module 1- Introduction
Master Theorem Limitations
The master theorem cannot be used if:

• T(n) is not monotone. eg. T(n) = sin n

• f(n) is not a polynomial. eg. f(n) = 2n

• a is not a constant. eg. a = 2n

• a<1

63 Module 1- Introduction
Using the master method
To use the master method, we simply determine which case of
the master theorem applies and write down the answer.

 Example,
T(n) = 9 T(n/3) + n
• Step 1 :
Compare given recurrence relation with standard form i.e.
T(n)=a T(n/b) + f(n) to
find out values of a, b and f(n).
So, we have a = 9, b = 3 , f(n) = n
• Step 2 :
Calculate value of n log b a using above values,
n log b a = n log 3 9 = n2

64 Module 1- Introduction
Using the master method (cont..)
• Step 3 :
Compare the values of function f(n) with the value of n log b a
Case 1 : If function n log b a is larger than f(n) then case 1 is
applicable, T(n) = Ө(n log b a )
Case 2 : If two functions are the same size then we multiply by a
logarithmic factor and
the solution is T(n) = Ө(n log b a lg n) = Ө( f(n ) lg n )
Case 3 : If function f(n) is larger than n log b a then case 3 is applicable,
T(n) = Ө( f(n ))

• Step 4 :
Based on this we get f(n) < n log b a so we can say for the given
example, case 1 is applicable so T(n) = Ө(n log b a )
T(n) = Ө( n2 )

65 Module 1- Introduction
Example 1 :
Q. Solve the given recurrence relation using Master Method
T(n) = 4 T(n/2) + n2 .
• Step 1 :
Compare given recurrence relation with standard form i.e. T(n)=a
T(n/b) + f(n) to
find out values of a, b and f(n).
So, we have a = 4, b = 2 , f(n) = n2

• Step 2 :
Calculate the value of n log b a using above values,
n log b a = n log 2 4
= n2 log 2 2
= n2

66 Module 1- Introduction
Example 1 (cont..) :
• Step 3 :
Compare the values of function f(n) with the value of n log b a .
f(n) = n2 and n log b a = n2
For given recurrence relation we have f(n) = n log b a
Hence case 2 is applicable i.e. If two functions are the
same size then we multiply by a logarithmic factor and
the solution is T(n) = Ө(n log b a log n) = Ө( f(n ) log n )

• Step 4 :
Based on this case 2 T(n) = Ө(n log b a log n )
T(n) = Ө( n2 log n )

67 Module 1- Introduction
Example 2 :
Q. Solve the given recurrence relation using Master Method
T(n) = 16 T(n/4) + n!.
• Step 1 :
Compare given recurrence relation with standard form i.e. T(n)=a
T(n/b) + f(n) to
find out values of a, b and f(n).
So, we have a = 16, b = 4 , f(n) = n!

• Step 2 :
Calculate the value of n log b a using above values,
n log b a = n log 4 16
= n2 log 4 4
= n2

68 Module 1- Introduction
Example 2 (cont..) :
• Step 3 :
Compare the values of function f(n) with the value of n log b a .
f(n) = n ! and n log b a = n2
For given recurrence relation we have f(n) > n log b a
Hence case 3 is applicable i.e. If function f(n) is larger than
n log b a then case 3 is applicable, T(n) = Ө( f(n ))

• Step 4 :
Based on this case 3 T(n) = Ө( f(n) )
T(n) = Ө( n! )

69 Module 1- Introduction
Example 3 :
Q. Solve the given recurrence relation using Master Method
T(n) = √2 T(n/2) + log n.
• Step 1 :
Compare given recurrence relation with standard form i.e. T(n)=a
T(n/b) + f(n) to
find out values of a, b and f(n).
So, we have a = √2 , b = 2 , f(n) = log n

• Step 2 :
Calculate the value of n log b a using above values,
n log b a = n log 2 √2
= n1/2 log 2 2
= n ½ = √n

70 Module 1- Introduction
Example 3 (cont..) :
• Step 3 :
Compare the values of function f(n) with the value of n log b a .
f(n) = log n and n log b a = √n
For given recurrence relation we have f(n) < n log b a
Hence case 1 is applicable i.e. If function n log b a is larger
than f(n) then case 1 is applicable, T(n) = Ө(n log b a )

• Step 4 :
Based on this case 1 T(n) = Ө(n log b a )
T(n) = Ө( √n )

71 Module 1- Introduction
Example 4 :
Q. Solve the given recurrence relation using Master Method
T(n) = 2n T(n/2) + nn.

• Step 1 :
Compare given recurrence relation with standard form i.e. T(n)=a T(n/b) +
f(n) to
find out values of a, b and f(n).
So, we have a = 2n, b = 2 , f(n) = nn
As per theorem value of ‘a’ should be constant and in given recurrence
relation value of ‘a’ keeps on changing for all n. Therefore, a is not constant.
Hence, Master Method can not be applied.

72 Module 1- Introduction
Example 5 :
Q. Solve the given recurrence relation using Master Method
T(n) = 0.5 T(n/2) + 1/n.

• Step 1 :
Compare given recurrence relation with standard form i.e. T(n)=a T(n/b) +
f(n) to
find out values of a, b and f(n).
So, we have a = 0.5, b = 2 , f(n) = 1/n
To apply master theorem value of a ≥ 1 and in given recurrence relation
value of a <1.
Hence, Master Method can not be applied.

73 Module 1- Introduction
 Example 6 :
Q. Solve the given recurrence relation using Master Method
T(n) = 64 T(n/8) – n2 log n.

• Step 1 :
Compare given recurrence relation with standard form i.e. T(n)=a T(n/b) +
f(n) to
find out values of a, b and f(n).
So, we have a = 64, b = 8 , f(n) = – n2 log n
To apply master theorem value of a ≥ 1 , b > 1and f(n) should be positive
function. But in given recurrence relation value of f(n) is not positive.
Hence, Master Method can not be applied.

74 Module 1- Introduction
 Practice Problems
1. T (n) = 3T (n/2) + n^2

2. T (n) = 4T (n/2) + n^2

3. T (n) = T (n/2) + 2^n

4. T (n) = 16T (n/4) + n

5. T (n) = 2T (n/2) + n log n

6. T (n) = 2T (n/4) + n 0.58

7. T (n) = 4T (n/2) + cn

8. T (n) = 3T (n/3) + n/2

9. T(n) = 4T(n/2) + n^2 + n

10. T(n) = T(n/2 + 5) + n^2

75 Module 1- Introduction
Activity

[Link]
KgMoz3M79CjW3TV7wJzxI9AfdNY/edit?usp=sharing

70 MLoedcutlu
e r1e
- IN
nto
rod5u:cM
tioa
n ster Theorem
Thank You