2CS503 Design &

Analysis
Unit-3 of Algorithm
Divide and Conquer
Algorithm
Recurrence Relation

Disclaimer: Content in the PPT is prepared from Books, videos and blogs
Topics to be covered
 Introduction to Recurrence Equation
 Different methods to solve recurrence
 Divide and Conquer Technique
 Multiplying large Integers Problem
 Problem Solving using divide and conquer algorithm –
1. Binary Search
2. Sorting (Merge Sort, Quick Sort)
3. Matrix Multiplication
4. Exponential

2
Introduction
 Many algorithms (divide and conquer) are recursive in nature.
 When we analyze them, we get a recurrence relation for time complexity.
 We get running time as a function of (input size) and we get the running time on inputs
of smaller sizes.
 A recurrence is a recursive description of a function, or a description of a function in
terms of itself.
Or
 A recurrence is an equation or inequality that describes a function in terms of its values
on smaller inputs.
Or
 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)
3
Methods to Solve Recurrence
 Substitution
 Homogeneous (characteristic equation)
 Non-homogeneous
 Master method
 Recurrence tree
 Intelligent guess work
 Change of variable
 Range transformations

4
Substitution Method
 We make a guess for the solution and then we use mathematical induction to prove the
guess is correct or incorrect.
 Example 1:
𝑇 (𝑛)=𝑇 (𝑛 − 1)+𝑛 1

 Replacing by and , we can write following equations.

𝑇 (𝑛 −1)=𝑇 (𝑛 −2)+𝑛 −1 2

𝑇 (𝑛 −2)=𝑇 (𝑛 − 3)+𝑛 −2 3
 Substituting equation in and equation in we have now,

𝑇 (𝑛)=𝑇 (𝑛 − 3)+ 𝑛− 2+𝑛 −1+𝑛 4

5
Substitution Method
𝑇 (𝑛)=𝑇 (𝑛 − 3)+ 𝑛− 2+𝑛 −1+𝑛 4
 From above, we can write the general form as,

𝑇 ( 𝑛 )=𝑇 ( 𝑛 − 𝑘) +(𝑛 −𝑘+1)+(𝑛 −𝑘+2)+…+𝑛

 Suppose, if we take then,

𝑇 (𝑛)=𝑇 (𝑛 −𝑛)+𝑛 −𝑛 +1+𝑛 −𝑛+ 2+…+𝑛

𝑇 ( 𝑛 )=0 +1+2+ …+𝑛

𝑛 (𝑛 +1 )
𝑇 ( 𝑛 )= = 𝑶 ( 𝒏𝟐 )
2
6
Exercise 1
Rewrite,
Now, replace by and

So,

In general,

Suppose if we take then,

7
Exercise 2
 Solve the following recurrence using substitution method.

8
Solving recurrence relation
• Iteration (already discussed in previous slids)
• Characteristics root
• Generating function

9
Homogeneous Recurrence
 Find the equation in terms of x, i.e., characteristic equation.
 Solve the characteristics equation and find the characteristic root.
 If characteristic roots are:
• r = r1, r2, r3 distinct => Sol: T(n) = c1.r1n + c2.r2n + c3.r3n
• r = r1 , r1 same => Sol: T(n) = (c1+n.c2)r1n
• r = r1 , r 1 , r 2 , r 3 => Sol: T(n) = (c1+n.c2)r1n + c3.r2n + c4.r3n
• r = r1 , r 1 , r 1 , r 2 => Sol: T(n) = (c1+n.c2+n2.c3)r1n + c4.r2n

10
Homogeneous Recurrence
 Recurrence equation

 The equation of degree in is called the characteristic equation of the recurrence,

{order=n-(n-k)=>k i.e. difference between highest and lowest }

11
Example
 T(n)= T(n-1) + 2 T(n-2) , n>=2, T(0) = 0, T(1) = 1
 T(n) - T(n-1) - 2 T(n-2) = 0

 T(n) = c1.2n + c2.(-1)n

 T(0) = 0, c1 + c2=0
 T(1) = 1, 2.c1 - c2=1
 c1= 1/3, c2= -1/3

 T(n)= 4(T(n-1) - T(n-2)) , n>=2, T(0) = 1, T(1) = 1

12
Analysis: Fibonacci series
Function fibiter(n)
i ← 1; j ← 0;
for k ← 1 to n do
j ← i + j;
i ← j – i;
return j

Iterative Algorithm for Fibonacci series: If we count all arithmetic

operations at unit cost; the instructions inside for loop take constant
time . The time taken by the for loop is bounded above by , .,

13
Analysis: Fibonacci series
 Recursive Algorithm for Fibonacci series,

Function fibrec(n)
if n < 2 then return n
else return fibrec (n – 1) + fibrec (n –
2)
 The recurrence equation of above algorithm is given as,

 The recurrence can be re-written as,

14
Analysis: Fibonacci series
−𝑏± √ 𝑏 −4𝑎𝑐
 The characteristic polynomial is, 2
𝑥=
 Whose roots are, 2𝑎
and
 The general solution is therefore of the form,
𝒌
 Substituting initial values and 𝒕 𝒏 =∑ 𝒄 𝒓 𝒏
𝒊 𝒊
𝒊=𝟏

15
Analysis: Fibonacci series
 Solving these equations, we obtain
and
 Substituting the values of roots and constants,

 Time taken for recursive Fibonacci algorithm grows exponentially.

16
Analysis: Tower of Hanoi

17
Analysis: Tower of Hanoi

18
Analysis: Tower of Hanoi
 The number of movements of a ring required in the tower of Hanoi problem is given by,

 The equation can be written as,

 To convert it into homogeneous equation,

• Multiply with -1 and replace m by m-1,

 Solving equations (1) and (2), we have now

19
Analysis: Tower of Hanoi
 The characteristic polynomial is,

 Whose roots are,

and
 The general solution is therefore of the form,

 Substituting initial values and

 Solving these linear equations we get c1 = -1 and c2 = 1.

 Therefore time complexity of tower of Hanoi problem is given as,
20
Non-homogeneous recurrence
Recurrence equation

is called as recurrence of order k, where a0,a1,a2,…ak are constants, it is also known as kth
order linear recurrence relation.
The solution of a given recurrence relation is given by:
Total solution or general solution := Homogeneous solution + Particular solution
T(n) = T(n)h+T(n)p

Homogeneous solution(T(n)h): we calculate homogeneous solution by

putting f(n)=0, and simply solves it.
T(n)h =>

21
Particular solution(T(n)p): it exist only when RHS of recurrence relation is
non-zero. i.e. f(n)≠0.
If f(n)≠0 we consider three possibility:
• Case1: f(n) is constant
• Case2: f(n) is polynomial of degree n
• Case3: f(n) is exponential

22
Particular solution(T(n)p) T(n)-2T(n-1)+T(n-2)=1

Case1: f(n) is constant => To calculate Particular solution

1. find p by putting
=> put T(n)=P
T(n)=p, => P-2(P)+P=1
2. If fails, put T(n)=np => 0=1 fail
3. If fails, put T(n)=n2p…
=> put T(n)=nP
=> nP-2(n-1)P+(n-2)P=1
=> 0=1 fail

=> put T(n)=n2P

=> n2P – 2(n-1)2P+(n-2)2P=1
=> p=1/2
=> Now put the value of P in solution
T(n)p=n2P=>n2/2

23
Particular solution(T(n)p) T(n)-8T(n-1) =14n+5

Case2: f(n) is polynomial => To calculate Particular solution

1. T(n)=d0+d1n+d2n2…dmnm
=> put T(n)= d0+d1n
2. Find d0, d1, d2.. by => d +d n – 8(d +d (n-1))=14n+5
comparing the co-efficient => -7d – 7d n+8d =5 + 14n
0 1 0 1

0 1 1
=> By comparing the coefficient of n0, n1 term
=> -7d1=14 => d1=-2
=> -7d0+8d1=5 =>d0= -3
Now put the value of d0 and d1 to get the solution
T(n)p=d0+d1n
T(n)p= -3 + (-2)n

24
Particular solution(T(n)p) T(n)-8T(n-1) =5 * 2n
f(n) is exponential function => To calculate Particular solution
Case3: (a)if a is not the characteristic
=> put T(n)= dan {a=2}
root
=> d*2n – 8*d2n-1=5*2n
 find d by putting T(n)=d0*an, => d*2n – 4*21*d2n-1=5*2n
 find d by putting T(n)= (d0+d1n) an if f(n) => d*2n – 4*d2n=5*2n
contain 1 order polynomial =>2n(d-4d)=5*2n
=> By comparing the coefficient of 2n
Case3: (b) if a is a characteristic root => d=-5/3
 find d by putting T(n)=nt *d0*an, Now put the value of d to get the
 find d by putting T(n)= nt (d0+d1n) an if f(n)
solution
T(n)p=dan
contain 1 order polynomial
T(n)p= -5/3* 2n
 t is the multiplicity of the root, i.e. 3, 3 are the
root => n2 as 3 repeat 2 times so value of t=2

25
 T(n)-7T(n-1)+12T(n-2) = 4n
 T(n)-7T(n-1)+12T(n-2) = n.4n

26
Find the total solution: T(n)-8T(n-1) =14n+5
1. Homogeneous solution(T(n)h) 2. Particular solution(T(n)p)
T(n)-8T(n-1)=0  => put T(n)= d0+d1n
characteristic equation  => d0+d1n – 8(d0+d1(n-1))=14n+5
X-8=0 , roots=(8) => -7d0 – 7d1n+8d1=5 + 14n
T(n)h = c18n

 => By comparing the coefficient of
n0, n1 term
 => -7d1=14 => d1=-2
 => -7d0+8d1=5 =>d0= -3
 Now put the value of d0 and d1 to
get the solution
 T(n)p=d0+d1n
 T(n)p= -3 + (-2)n

Total solution(T(n))=(T(n)h) + (T(n)h)

T(n) = c18n -3 + (-2).n

27
Master Method(for divide and conquer recurrence)
 All divide and conquer algorithm divide the problem into sub-problems, each of which is part of
the original problem, and then perform some additional work to compute the final answer..
 Suppose you have a recurrence of the form
Time to divide &
recombine

Number of sub- Time required to

problems solve a sub-problem

 This recurrence would arise in the analysis of a recursive algorithm.

 When input size is large, the problem is divided up into sub-problems each of size . Sub-problems
are solved recursively and results are recombined.
 The work to split the problem into sub-problems and recombine the results is .
28
Master Method(for divide and conquer recurrence)
As an example, a merge sort algorithm operates on two sub-problems, each of which is
half the size of the original, and then performs O(n) additional work for merging. This gives
the running time equation:
T(n) = 2T (n/2) + O(n)

The following theorem can be used to determine the running time of divide and
conquer algorithms. For a given program (algorithm), first we try to find the recurrence
relation for the problem. If the recurrence is of the below form, then we can directly give the
answer without fully solving it. If the recurrence is of the form

29
Master Method(for divide and conquer recurrence)

where a ≥ 1, b >1, k ≥ 0 and p is a real number, then:

30
1.

31
2.

32
3.

33
4.

34
5.

35
6.

36
7.

37
8.

38
9.

39
10.

We can not apply master method in such cases

40
Master Method
 Example 4:
 Example 5:
 Example 6:
 Example 7:
 Example 8:
 Example 9:

41
Master Theorem for Subtract and Conquer Recurrences
Let T(n) be a function defined on positive n, and having the property
T(n)
for some constants c,a > 0,b ≥ 0,k ≥ 0, and function f(n). If f(n) is in
O(nk ), then

42
Recurrence Tree Method
Steps to solve recurrence relations using recursion tree method:

Step-01: Draw a recursion tree based on the given recurrence relation.

Step-02: Determine-
o Cost of each level
o Total number of levels in the recursion tree
o Number of nodes in the last level
o Cost of the last level

Step-03: total cost = cost of leaf node + cost of internal node

total cost = (cost of 1 leaf node* total leaf node) + sum of cost at each level of internal node
total cost = Lc + Ic

43
Important formula

44
Recurrence Tree Method
 Here while solving recurrences, we divide the problem into sub-problems of equal size.
 E.g., where and is a given function.
 is the cost of splitting or combining the sub problems.

𝑛/𝑏 𝑛/𝑏

45
Recurrence Tree Method
 Example 1:
 The recursion tree for this recurrence is :

𝑛
log 2 𝑛
𝑛/2 𝑛/2 𝑛

2 2 2 2 𝑛
𝑛/2 𝑛/2 𝑛/2 𝑛/2

1 1 1 1 1
46
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.
The given recurrence relation shows-
• The cost of dividing a problem of size n into its 2 sub-problems and then combining its solution is n.
• The cost of dividing a problem of size n/2 into its 2 sub-problems and then combining its solution is n/2 and so on.

Step-02:
• Determine cost of each level-
• Cost of level-0 = n
• Cost of level-1 = n/2 + n/2 = n
• Cost of level-2 = n/4 + n/4 + n/4 + n/4 = n and so on.

47
Step-03:
• Determine total number of levels in the recursion tree-
• Size of sub-problem at level-0 = n/20
• Size of sub-problem at level-1 = n/21
• Size of sub-problem at level-2 = n/22
• Continuing in similar manner, we have- Size of sub-problem at level-i = n/2i
• Suppose at level-x (last level), size of sub-problem becomes 1. Then- n / 2x = 1
• 2x = n
• Taking log on both sides, we get- xlog22 = log2n
• x = log2n
• ∴ Total number of levels in the recursion tree = log2n + 1

Step-04:
• Determine number of nodes in the last level-
• Level-0 has 20 nodes i.e. 1 node
• Level-1 has 21 nodes i.e. 2 nodes
• Level-2 has 22 nodes i.e. 4 nodes
• Continuing in similar manner, we have- Level-log2n, has 2log2n nodes i.e. n nodes
48
Step-05: Determine cost of last level-
Cost of last level = n x T(1) = θ(n)
Step-06:
Add costs of all the levels of the recursion tree and simplify the expression so obtained in terms of asymptotic
notation-

= n x log2n + θ (n)
= nlog2n + θ (n)
= θ (nlog2n)
49
Recurrence Tree Method
 When we add the values across the levels of the recursion tree, we get a value of for
every level.
 The bottom level has nodes, each contributing the cost
 We have

50
Recurrence Tree Method
 Example 2:
 The recursion tree for this recurrence is :

𝑛
log 3 𝑛 𝑛/3 2𝑛/3 𝑛 log 3/2𝑛

1 𝑛 2 𝑛 1 2𝑛 2 2𝑛 𝑛
3 3 3 3 3 3 3 3

51
Recurrence Tree Method

52
Recurrence Tree Method
 Example 2:
 The recursion tree for this recurrence is :

2
𝑛
2 2
( 𝑛/2 ) ( 𝑛/2 )
2
𝑐 .𝑛

2 2 2 2
( 𝑛/4 ) ( 𝑛/4 ) ( 𝑛/4 ) ( 𝑛/4 )
2
𝑐.1/2𝑛

𝑂 ( 𝑛2 )
53
Recurrence Tree Method
 Sub-problem size at levelis
 Cost of problem at level Is
 Total cost,

54
Recurrence Tree Method
 Example 3:
 Example 4:
 Example 5:

55
Method of Guessing and Confirming
“guess the answer; and then prove it correct by induction”

What if the given recurrence doesn’t seem to match with any of these (master theorem)
methods? If we guess a solution and then try to verify our guess inductively, usually either
the proof will succeed (in which case we are done), or the proof will fail (in which case the
failure will help us refine our guess).

56
Example

Let’s start by trying to prove an upper bound T(n) < c.nlogn:

The last inequality assumes only that 1 ≤ c.logn. This is correct if n is sufficiently large and for any
constant c, no matter how small. From the above proof, we can see that our guess is correct for the
upper bound.

57
Change of variable-Method
 There are many ways to solve a recurrence relation runtime. One way to do this is a
method called “change of variable”.
 Domain transformations can sometimes be used to substitute a function for the
argument of the relation and make it easier to solve.
 The idea is to select a function for S(m), when given T(n).

58
m=logn
n=2m , The reason to put n=2m is as the original function consists of
Example √𝐧 , i.e. the problem of size n is decreasing with factor n 1/2
2m=2log2n
2m/2=2(log2n/2)

T(n)=2T +logn
T(2m)= S(m) meaning the rate of growth for different value of m is
same for T and S 2m/2=n1/2

Let’s rewrite the equation by substituting m=log n, and then plug it back in to the
recurrence to get the following:
T(2m)=2T(2m/2)+m
Now we will create a new function called ‘S’ that takes in a parameter ‘m’ such that
S(m) = T(2m). Let S(m) =
Which means : S(m) = 2T(2m/2)+m. T(2m)
S(1) = T(21)
If S(m) = T(2 ) then S(m-1) = T(2
m (m-1
)) and S(m/2) = T(2 (m/2)
),
S(2) = T(22)
so we can rewrite our function to get the following: S(m-1) = T(2m-1)
S(m)=2S(m/2)+m S(m/2) = T(2m/2)

Using master theorem we can write the solution of recurrence ‘S’: O(mlogm).
This means that our original function ‘T’ belongs to O(log n * log ( log n) ), since we can
simply replace ‘m’ with ‘log n’ because m=log n

59
Example
T(n)=T() +n
=>First substitute n = 2m
T(2m)=2m/2T(2m/2)+2m
Now divide both side by 2m
=+

=+ { =+}

=>second substitution S(m)=

S(m)=S(m/2)+1
By applying masters method we get : S(m)= log m
Now back substitution => =log m
T(2m)=2m log m
Again back-substitute: T(n)=n log log n
60
 T(n)=3T(n/2) +n
Substitute n=2m
T(2m)=3T(2m/2)+2m
T(2m)=3T(2m-1)+2m
Substitute S(m)=T(2m)
S(m)=3S(m-1)+2m
S(m)-3S(m-1)=2m
By characteristic equation
x-3=0, x=3
T(m)h=c13m
T(m)p=(-3/2)2m
Total Solution of S(m)=c13m-(3/2)2m
By back substitution
T(n)=c13logn-(3/2)2logn
=c1nlog3-(3/2)2nlog2
61
Range transformation
 When we make a change of variable, we transform the domain of the recurrence.
 Instead, it may be useful to transform the range to obtain a recurrence in a form that we know
how to solve. Both transformations can sometimes be used together.

Consider the following recurrence, which defines T(n) when n is a power of 2.

T(n)=nT2(n/2)
The first step is a change of variable: n=2m, S(m)=T(2m)
T(2m)= 2m T2(2m/2)=> T2(2m-1)
S(m)=2m S2(m-1)
 At first glance, none of the techniques we have seen applies to this recurrence since it is not
linear; To transform the range, we create yet another recurrence by using U(m) to denote log
S(m).
62
S(m)=2m S2(m-1)
Substitute U(m)=log(S(m))
=log(2m S2(m-1))
=log2m + log S2(m-1)
=m+2log S(m-1)
=m+2U(m-1)
U(m)= m+2U(m-1)
U(m)-2U(m-1)=m
Solve this by applying Characteristic equation:

63
Divide & Conquer (D&C) Technique
 Many useful algorithms are recursive in structure: to solve a given problem, they call
themselves recursively one or more times.
 These algorithms typically follow a divide-and-conquer approach:
 The divide-and-conquer approach involves three steps at each level of the recursion:
1. Divide: Break the problem into several sub problems that are similar to the original problem
but smaller in size.
2. Conquer: Solve the sub problems recursively. If the sub problem sizes are small enough, just
solve the sub problems in a straightforward manner.
3. Combine: Combine these solutions to create a solution to the original problem.

64
D&C: Running Time Analysis
 The running-time analysis of such divide-and-conquer (D&C) algorithms is almost
automatic.
 Let be the time required by D&C on instances of size .
 The total time taken by this divide-and-conquer algorithm is given by recurrence
equation,

 The solution of equation is given as,

is the power of in
65