Analysis and Design of Algorithms (ADA)

GTU # 3150703

Unit-3:
Divide and Conquer
Algorithms
 Outline
Looping
▪ Introduction to Recurrence Equation
▪ Different methods to solve recurrence
▪ Divide and Conquer Technique
▪ Multiplying large Integers Problem
▪ Problem Solving using divide and conquer
algorithm –
✓ Binary Search
✓ Sorting (Merge Sort, Quick Sort)
✓ Matrix Multiplication
✓ Exponential
Recurrence Equation
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.
 A recurrence relation recursively defines a sequence where the next term is a function of the
previous terms.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 4

Methods to Solve Recurrence
 Substitution
 Homogeneous (characteristic equation)
 Inhomogeneous
 Master method
 Recurrence tree
 Intelligent guess work
 Change of variable
 Range transformations

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 5

Substitution Method – Example 1
 We make a guess for the solution and then we use mathematical induction to prove the guess
is correct or incorrect.
Time to solve the
Example 1: instance of size 𝑛 − 1

𝑻(𝒏) = 𝑻(𝒏 − 𝟏) + 𝒏 1

 Replacing 𝑛Time
by 𝑛to − 1 and
solve the 𝑛 − 2, we can write following equations.
instance of size 𝑛
𝑻 𝒏−𝟏 =𝑻 𝒏−𝟐 +𝒏−𝟏 2

𝑻 𝒏−𝟐 =𝑻 𝒏−𝟑 +𝒏−𝟐 3

 Substituting equation 3 in 2 and equation 2 in 1 we have now,

𝑻(𝒏) = 𝑻(𝒏 − 𝟑) + 𝒏 − 𝟐 + 𝒏 − 𝟏 + 𝒏 4
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 6
Substitution Method – Example 1

𝑻(𝒏) = 𝑻(𝒏 − 𝟑) + 𝒏 − 𝟐 + 𝒏 − 𝟏 + 𝒏 4

 From above, we can write the general form as,

𝑻 𝒏 = 𝑻 𝒏 − 𝒌 + (𝒏 − 𝒌 + 𝟏) + (𝒏 − 𝒌 + 𝟐) + … + 𝒏

 Suppose, if we take 𝑘 = 𝑛 then,

𝑻 𝒏 = 𝑻 𝒏 − 𝒏 + (𝒏 − 𝒏 + 𝟏) + (𝒏 − 𝒏 + 𝟐) + … + 𝒏

𝑻 𝒏 = 𝟎 +𝟏 + 𝟐 + …+𝒏

𝒏 𝒏+𝟏
𝑻 𝒏 = = 𝑶 𝒏𝟐
𝟐
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 7
Substitution Method – Example 2
𝑐1 𝑖𝑓 𝑛 = 0
𝑡 𝑛 =ቊ
𝑐2 + 𝑡 𝑛 − 1 𝑜/𝑤

 Rewrite the equation, 𝑡 𝑛 = 𝑐2 + 𝑡(𝑛 − 1)

 Now, replace 𝐧 by 𝐧 – 𝟏 and 𝐧 − 𝟐
𝑡 𝑛 − 1 = 𝑐2 + 𝑡(𝑛 − 2) ∴ 𝑡 𝑛 − 1 = 𝑐2 + 𝑐2 + 𝑡(𝑛 − 3)
𝑡 𝑛 − 2 = 𝑐2 + 𝑡(𝑛 − 3)
 Substitute the values of 𝐧 – 𝟏 and 𝐧 − 𝟐
𝑡 𝑛 = 𝑐2 + 𝑐2 + 𝑐2 + 𝑡(𝑛 − 3)
 In general,
𝑡 𝑛 = 𝑘𝑐2 + 𝑡(𝑛 − 𝑘)
 Suppose if we take 𝑘 = 𝑛 then,
𝑡 𝑛 = 𝑛𝑐2 + 𝑡 𝑛 − 𝑛 = 𝑛𝑐2 + 𝑡 0
𝑡(𝑛) = 𝑛𝑐2 + 𝑐1 = 𝑶 𝒏
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 8
Substitution Method Exercises
 Solve the following recurrences using substitution method.

1 if n = 0 or 1
1. T n = ቊ
T n − 1 + n − 1 o/w

2. T (n) = T (n − 1) + 1 and T (1) = θ (1).

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 9

Homogeneous Recurrence
 Recurrence equation
𝑎0 𝑡𝑛 + 𝑎1 𝑡𝑛−1 + 𝑎2 𝑡𝑛−2 + ⋯ + 𝑎𝑘 𝑡𝑛−𝑘 = 0
 The equation of degree 𝑘 in 𝑥 is called the characteristic equation of the recurrence,
𝑝 𝑥 = 𝑎0 𝑥 𝑘 + 𝑎1 𝑥 𝑘−1 + ⋯ + 𝑎𝑘 𝑥 0
 Which can be factorized as,
𝑘

𝑝 𝑥 = ෑ 𝑥 − 𝑟𝑖
𝑖=1
 The solution of recurrence is given as,
𝒌

𝒕𝒏 = ෍ 𝒄𝒊 𝒓𝒏𝒊
𝒊=𝟏

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 10

Homogeneous Recurrence – Example 1 : Fibonacci Series
 Fibonacci series Iterative Algorithm

Function fibiter(n)
i ← 1; j ← 0;
for k ← 1 to n do
j ← i + j;
i ← j – i;
return j

 Analysis of Iterative Algorithm: 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 𝑛, 𝑖. 𝑒., 𝒏𝒄 = 𝛉(𝒏)
Case 1
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 11
Homogeneous Recurrence – Example 1 : Fibonacci Series
 If the value of 𝒏 is large, then time needed to execute addition operation increases linearly with
the length of operand.
 At the end of 𝑘𝑡ℎ iteration, the value of 𝒊 and 𝒋 will be 𝒇𝒌−𝟏 and 𝒇𝒌.
 As per De Moivre’s formula the size of 𝒇𝒌 is in 𝜽(𝒌).
 So, 𝒌𝒕𝒉 iteration takes time in 𝜽(𝒌). let 𝒄 be some constant such that this time is bounded
above by 𝒄𝒌 for all 𝒌 ≥ 𝟏.
 The time taken by fibiter algorithm is bounded above by,
𝑛 𝑛
𝑛 𝑛+1
෍ 𝑐. 𝑘 = 𝑐. ෍ 𝑘 = 𝑐.
2
𝑘=1 𝑘=1

𝑻 𝒏 = 𝜽 𝒏𝟐
Case 2

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 12

Homogeneous Recurrence – Example 1 : 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,

𝑇 𝑛 −𝑇 𝑛−1 −𝑇 𝑛−2 =0
 The characteristic polynomial is,
𝑥2 − 𝑥 − 1 = 0
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 13
Homogeneous Recurrence – Example 1 : Fibonacci Series
 Find the roots of characteristic polynomial,
𝑥2 − 𝑥 − 1 = 0 −𝒃 ± 𝒃𝟐 − 𝟒𝒂𝒄
𝒙 =
𝟐𝒂
 The roots are, Here, 𝒂 = 𝟏, 𝒃 = 𝟏 and
1+ 5 1− 5 𝒄=𝟏
𝑟1 = and 𝑟2 =
2 2

𝒌
 The general solution is therefore of the form, 𝒏
𝒏 𝒏
𝑻𝒏 = 𝒄𝟏 𝒓𝟏 + 𝒄𝟐 𝒓𝟐 𝑻 𝒏 = ෍ 𝒄 𝒊 𝒓𝒊
𝒊=𝟏
 Substituting initial values 𝑛 = 0 and 𝑛 = 1
𝑇0 = 𝑐1 + 𝑐2 = 0 1
𝑇1 = 𝑐1 𝑟1 + 𝑐2 𝑟2 = 1 (2)
 Solving these equations, we obtain
1 1
𝑐1 = and 𝑐2 = −
5 5

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 14

Homogeneous Recurrence – Example 1 : Fibonacci Series
 Substituting the values of roots and constants in general solution,

𝑻𝒏 = 𝒄𝟏 𝒓𝒏𝟏 + 𝒄𝟐 𝒓𝒏𝟐

𝑛 𝑛
1 1+ 5 1− 5
𝑇𝑛 = − … … … de Moivre′ s formula
5 2 2

𝒏
𝑻𝒏 ∈ 𝑶 ∅

 Time taken for recursive Fibonacci algorithm grows Exponentially.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 15

Example 2 : Tower of Hanoi
tower 1 tower 2 tower 3

tower 1 tower 2 tower 3

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 16

Example 2 : 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,

𝒕 𝒎 − 𝟐𝒕 𝒎 − 𝟏 = 𝟏 (𝟏) Inhomogeneous equation

 To convert it into a homogeneous equation, multiply with −𝟏 and replace 𝐦 by 𝐦 − 𝟏,

−𝒕 𝒎 − 𝟏 + 𝟐𝒕 𝒎 − 𝟐 = −𝟏 (𝟐)

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

𝒕 𝒎 − 𝟑𝒕 𝒎 − 𝟏 + 𝟐𝒕(𝒎 − 𝟐) = 𝟎

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 17

Example 2 : 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 𝒄𝟏 = −𝟏 and 𝒄𝟐 = 𝟏.
 Therefore, time complexity of tower of Hanoi problem is given as,

𝒕 𝒎 = 𝟐𝒎 − 𝟏 = 𝑶 𝟐𝒎
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 18
Homogeneous Recurrence Exercises
 Solve the following recurrences

𝑛 𝑖𝑓 𝑛 = 0 𝑜𝑟 1
1. 𝑡𝑛 = ቊ5𝑡
𝑛−1 − 6𝑡𝑛−2 𝑂/𝑊

𝑛 𝑖𝑓 𝑛 = 0, 1 𝑜𝑟 2
2. 𝑡𝑛 = ቊ
5𝑡𝑛−1 − 8𝑡𝑛−2 + 4𝑡𝑛−3 𝑜/𝑤

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 19

Master Theorem
 The master theorem is a cookbook method for solving recurrences.
Time to divide &
 Suppose you have a recurrence of the form 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 𝒇(𝒏).

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 20

Master Theorem – Example 1

𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛)

 There are three cases:
1. 𝑐𝑎𝑠𝑒 1: 𝑖𝑓 𝑓 𝑛 𝑖𝑠 𝑖𝑛 𝑶 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑓 𝑛 ≤ 𝑛log𝑏 𝑎 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎
2. 𝑐𝑎𝑠𝑒 2: 𝑓 𝑛 𝑖𝑠 𝑖𝑛 𝜽 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑓 𝑛 = 𝑛log𝑏 𝑎 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑙𝑔𝑛
3. 𝑐𝑎𝑠𝑒 3: 𝑓 𝑛 𝑖𝑠 𝑖𝑛 Ω 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑓 𝑛 ≥ 𝑛log𝑏 𝑎 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑓(𝑛)

 Example 1: 𝑇(𝑛) = 2𝑇(𝑛/2) + θ(𝑛) Merge sort

 Here 𝑎 = 2, 𝑏 = 2. So, 𝑛𝑙𝑜𝑔𝑏 𝑎 = 𝑛
 Also, 𝑓(𝑛) = 𝜃(𝑛) = c𝑛
 Case 2 applies: 𝑻 𝒏 = 𝜽 𝒏 𝒍𝒈𝒏

#3150703 (ADA)  Unit 3 – Divide and Conquer Algorithms 21

Master Theorem – Example 2

𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛)

 There are three cases:
1. 𝑐𝑎𝑠𝑒 1: 𝑖𝑓 𝑓 𝑛 𝑖𝑠 𝑖𝑛 𝑶 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑓 𝑛 ≤ 𝑛log𝑏 𝑎 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎
2. 𝑐𝑎𝑠𝑒 2: 𝑓 𝑛 𝑖𝑠 𝑖𝑛 𝜽 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑓 𝑛 = 𝑛log𝑏 𝑎 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑙𝑔𝑛
3. 𝑐𝑎𝑠𝑒 3: 𝑓 𝑛 𝑖𝑠 𝑖𝑛 Ω 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑓 𝑛 ≥ 𝑛log𝑏 𝑎 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑓(𝑛)

 Example 2: 𝑇(𝑛) = 𝑇(𝑛/2) + θ(1) Binary Search

 Here 𝑎 = 1, 𝑏 = 2. So, 𝑛𝑙𝑜𝑔𝑏 𝑎 = 𝑛log2 1 = 𝑛0 = 1
𝑓 𝑛 =θ 1 =1
 Case 2 applies: the solution is 𝜽(𝒏𝒍𝒐𝒈𝒃 𝒂 𝒍𝒐𝒈𝒏)
 𝑻 𝒏 = 𝜽(𝒍𝒐𝒈𝒏)

#3150703 (ADA)  Unit 3 – Divide and Conquer Algorithms 22

Master Theorem – Example 3

𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛)

 There are three cases:
1. 𝑐𝑎𝑠𝑒 1: 𝑖𝑓 𝑓 𝑛 𝑖𝑠 𝑖𝑛 𝑶 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑓 𝑛 ≤ 𝑛log𝑏 𝑎 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎
2. 𝑐𝑎𝑠𝑒 2: 𝑓 𝑛 𝑖𝑠 𝑖𝑛 𝜽 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑓 𝑛 = 𝑛log𝑏 𝑎 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑙𝑔𝑛
3. 𝑐𝑎𝑠𝑒 3: 𝑓 𝑛 𝑖𝑠 𝑖𝑛 Ω 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑓 𝑛 ≥ 𝑛log𝑏 𝑎 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑓(𝑛)

 Example 3: 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛

 Here 𝑎 = 4, 𝑏 = 2. So, 𝑙𝑜𝑔𝑏𝑎 = 2 and 𝑛logb a = 𝑛2
 𝑓 𝑛 = 𝑛,
 So, 𝑓(𝑛) ≤ 𝑛2 ⇒ 𝑓(𝑛) is in 𝑂(𝑛logb a )
 Case 1 applies: 𝑻(𝒏) = 𝜽(𝒏𝟐)

#3150703 (ADA)  Unit 3 – Divide and Conquer Algorithms 23

Master Theorem Exercises
 Example 4: 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛2
 Example 5: 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛3
 Example 6: 𝑇(𝑛) = 9𝑇(𝑛/3) + 𝑛 (Summer 17, Summer 19)
 Example 7: 𝑇(𝑛) = 𝑇(2𝑛/3) + 1 (Summer 17)
 Example 8: 𝑇 𝑛 = 7𝑇 𝑛Τ2 + 𝑛3 (Winter 18)
 Example 9: 𝑇(𝑛) = 27𝑇(𝑛2 ) + 16𝑛 (Winter 19)

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 24

Recurrence Tree Method
 In recurrence tree, each node represents the cost of a single sub-problem in the set of
recursive function invocations.
 We sum the costs within each level of the tree to obtain a set of per level costs.
 Then we sum the all the per level costs to determine the total cost of all levels of the recursion.
 Here while solving recurrences, we divide the problem into sub-problems of equal size.
 E.g., 𝑇(𝑛) = 𝑎 𝑇(𝑛/𝑏) + 𝑓(𝑛) where 𝑎 > 1 , 𝑏 > 1 and 𝑓(𝑛) is a given function.
 𝐹(𝑛) is the cost of splitting or combining the sub problems.

𝒏Τ𝒃 𝒏Τ𝒃

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 25

 Example 1: 𝑻(𝒏) = 𝟐𝑻(𝒏/𝟐) + 𝒏
Recurrence Tree Method
The recursion tree for this recurrence is ▪ When we add the values across the levels of
the recursion tree, we get a value of 𝑛 for
every level.
𝑛
▪ The bottom level has 2log 𝑛 nodes, each
contributing the cost 𝑇(1).
𝑛 Τ2 𝑛 Τ2 𝒏
𝒍𝒐𝒈𝟐 𝒏 ▪ We have 𝑛 + 𝑛 + 𝑛 + …… log 𝑛
𝑡𝑖𝑚𝑒𝑠
𝒍𝒐𝒈𝟐 𝒏−𝟏
𝑛 Τ22 𝑛 Τ22 𝑛 Τ22 𝑛 Τ22 𝒏
𝑻(𝒏) = ෍ 𝒏 + 𝟐𝒍𝒐𝒈 𝒏 𝑻(𝟏)
𝒊=𝟎

1 1 1 1 𝑻 𝒏 = 𝒏 𝒍𝒐𝒈 𝒏 + 𝒏

𝑻 𝒏 = 𝑶(𝒏 log 𝒏)
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 26
 Example 2: 𝑻(𝒏) = 𝑻(𝒏/𝟑) + 𝑻(𝟐𝒏/𝟑) + 𝒏
Recurrence Tree Method
The recursion tree for this recurrence is ▪ When we add the values across the levels of
the recursion tree, we get a value of 𝑛 for
every level.

log3/2 𝑛−1
𝑛
𝑇(𝑛) = ෍ 𝑛 + 𝑛log3/2 2 𝑇(1)
𝑖=0

𝑛Τ3 2𝑛Τ3 𝒏
𝒍𝒐𝒈𝟑 𝒏 𝒍𝒐𝒈𝟑/𝟐 𝒏 𝑻(𝒏) ∈ 𝒏 log 𝟑/𝟐 𝒏

1𝑛 2𝑛 1 2𝑛 2 2𝑛 𝒏
33 33 3 3 3 3

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 27

 Example 3: 𝑻(𝒏) = 𝟐𝑻(𝒏/𝟐) + 𝒄. 𝒏𝟐
Recurrence Tree Method
The recursion tree for this recurrence is ▪ Sub-problem size at level 𝑖 is 𝑛Τ2𝑖
2
▪ Cost of problem at level 𝑖 Is 𝑛
Τ2𝑖
▪ Total cost,
𝒍𝒐𝒈𝟐 𝒏−𝟏 𝒊
𝟏
𝑛2 𝑻 𝒏 ≤ 𝒏𝟐 ෍
𝟐
𝒊=𝟎

∞
𝑛Τ2 2
𝑛 Τ2 2 1Τ2 𝑛2 𝟏
𝒊
𝟐
𝑻 𝒏 ≤𝒏 ෍
𝟐
𝒊=𝟎

𝑛 Τ4 2 𝑛 Τ4 2 𝑛 Τ4 2 𝑛 Τ4 2 1Τ4 𝑛2 𝑻 𝒏 ≤ 𝟐𝒏𝟐

𝑻 𝒏 = 𝑶 𝒏𝟐
𝑂 𝑛2
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 28
Recurrence Tree Method - Exercises
 Example 1: 𝑇(𝑛) = 𝑇(𝑛/4) + 𝑇(3𝑛/4) + 𝑐. 𝑛
 Example 2: 𝑇(𝑛) = 3𝑇(𝑛/4) + 𝑐. 𝑛2
 Example 3: 𝑇(𝑛) = 𝑇(𝑛/4) + 𝑇(𝑛/2) + 𝑛2
 Example 4: 𝑇(𝑛) = 𝑇(𝑛/3) + 𝑇(2𝑛/3) + 𝑛

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 29

Divide & Conquer (D&C)
Technique
Introduction
 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.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 31

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,
𝑡 𝑛 = 𝑙𝑡 𝑛/𝑏 + g 𝑛 𝐓(𝐧) = 𝐚𝐓(𝐧/𝐛) + 𝐟(𝐧)

 The solution of equation is given as,

𝜃 𝑛𝑘 𝑖𝑓 𝑙 < 𝑏 𝑘
𝑡 𝑛 = 𝜃 𝑛𝑘 𝑙𝑜𝑔𝑛 𝑖𝑓 𝑙 = 𝑏 𝑘
𝜃 𝑛𝑙𝑜𝑔𝑏 𝑙 𝑖𝑓 𝑙 > 𝑏 𝑘
where 𝑘 is the power of 𝑛 in 𝑔(𝑛)

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 32

Binary Search
Introduction
 Binary Search is an extremely well-known instance of divide-and-conquer approach.
 Let 𝑇[1 . . . 𝑛] be an array of increasing sorted order; that is 𝑇 [𝑖] ≤ 𝑇[𝑗] whenever 1 ≤ 𝑖 ≤
𝑗 ≤ 𝑛.
 Let 𝑥 be some number. The problem consists of finding 𝒙 in the array 𝑇 if it is there.
 If 𝑥 is not in the array, then we want to find the position where it might be inserted.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 34

Binary Search Example

Input: sorted array of integer values. 𝒙 = 𝟕

1 3 7 9 11 32 52 74 90

Step 1:
1 2 3 4 5 6 7 8 9

1 3 7 9 11 32 52 74 90

Find approximate midpoint

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 35
Binary Search Example
Step 2:
1 2 3 4 5 6 7 8 9 𝒙=𝟕

1 3 7 9 11 32 52 74 90

IsIs𝟕𝟕< =midpoint
midpointvalue?
value?YES.
No.
Step 3:
1 2 3 4 5 6 7 8 9

1 3 7 9 11 32 52 74 90

Search for the target in the area before midpoint.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 36
Binary Search Example
Step 4:
1 2 3 4 5 6 7 8 9 𝒙=𝟕

1 3 7 9 11 32 52 74 90

Find approximate midpoint

Step 5:
1 2 3 4 5 6 7 8 9

1 3 7 9 11 32 52 74 90

𝟕 > value of midpoint? YES.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 37
Binary Search Example
Step 6:
1 2 3 4 5 6 7 8 9 𝒙=𝟕

1 3 7 9 11 32 52 74 90

Search for the 𝒙 in the area after midpoint.

Step 7:
1 2 3 4 5 6 7 8 9

1 3 7 9 11 32 52 74 90

Find approximate midpoint.

Is 𝒙 = midpoint value? YES.
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 38
Binary Search – Iterative Algorithm
Algorithm: Function biniter(T[1,…,n], x)
𝑛=7 𝑥𝑥==33
7
if x > T[n] then return n+1
i ← 1; i 3
j ← n; 6
while i < j do
7
k ← (i + j ) ÷ 2
k 11
if x ≤ T [k] then j ← k
else i ← k + 1 32
return i 33
j 53

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 39

Binary Search – Recursive Algorithm
Algorithm: Function binsearch(T[1,…,n], x)
if n = 0 or x > T[n] then return n + 1
else return binrec(T[1,…,n], x)
Function binrec(T[i,…,j], x)
if i = j then return i
k ← (i + j) ÷ 2
if x ≤ T[k] then
return binrec(T[i,…,k],x)
else return binrec(T[k + 1,…,j], x)

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 40

Binary Search - Analysis
 Let 𝑡(𝑛) be the time required for a call on binrec( 𝑇[𝑖, … , 𝑗], 𝑥 ), where 𝑛 = 𝑗 – 𝑖 + 1 is the
number of elements still under consideration in the search.
 The recurrence equation is given as,
𝒕(𝒏) = 𝒕(𝒏/𝟐) + 𝜽(𝟏) 𝑻(𝒏) = 𝒂𝑻(𝒏/𝒃) + 𝒇(𝒏)
 Comparing this to the general template for divide and conquer algorithm, 𝑎 = 1, 𝑏 =
2 𝑎𝑛𝑑 𝑓 𝑛 = 𝜃 1 .
∴ 𝒕(𝒏) ∈ 𝜽(𝒍𝒐𝒈 𝒏)
 The complexity of binary search is 𝜽(𝒍𝒐𝒈 𝒏)

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 41

Binary Search – Examples
1. Demonstrate binary search algorithm and find the element 𝒙 = 𝟏𝟐 in the following array. [3 /
4]
2, 5, 8, 12, 16, 23, 38, 56, 72, 91

2. Explain binary search algorithm and find the element 𝒙 = 𝟑𝟏 in the following array. [7]
10, 15, 18, 26, 27, 31, 38, 45, 59

3. Let 𝑻[𝟏. . 𝒏] be a sorted array of distinct integers. Give an algorithm that can find an index 𝒊
such that 𝟏 ≤ 𝒊 ≤ 𝒏 and 𝑻[𝒊] = 𝒊, provided such an index exists. Prove that your
algorithm takes time in 𝑂(𝑙𝑜𝑔𝑛) in the worst case.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 42

Multiplying Large Integers
Multiplying Large Integers – Introduction
 Multiplying two 𝑛 digit large integers using divide and conquer method.
 Example: Multiplication of 𝟗𝟖𝟏 by 𝟏𝟐𝟑𝟒.
1. Convert both the numbers into same length nos. and split each operand into two parts:

𝟎𝟗𝟖𝟏 𝟏𝟐𝟑𝟒

𝒘 = 𝟎𝟗 𝒙 = 𝟖𝟏 𝒚 = 𝟏𝟐 𝒛 = 𝟑𝟒
2. We can write as,

102𝑤 + 𝑥 𝟎𝟗𝟖𝟏 = 𝟏𝟎𝟐 𝒘 + 𝒙 𝟏𝟐𝟑𝟒 = 𝟏𝟎𝟐 𝒚 + 𝒛

= 102 09 + 81
= 900 + 81
=981

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 44

Multiplying Large Integers – Example 1
 Now, the required product can be computed as,
0981 × 1234 = 102 𝑤 + 𝑥 × 102 𝑦 + 𝑧 𝑤 = 09
= 104 𝑤 ∙ 𝑦 + 102 𝑤 ∙ 𝑧 + 𝑥 ∙ 𝑦 + 𝑥 ∙ 𝑧 𝑥 = 81
= 1080000 + 127800 + 2754 𝑦 = 12
= 1210554 𝑧 = 34

 The above procedure still needs four half-size multiplications:

𝑖 𝑤 ∙ 𝑦 𝑖𝑖)𝑤 ∙ 𝑧 𝑖𝑖𝑖 𝑥 ∙ 𝑦 (𝑖𝑣 𝑥 ∙ 𝑧
 The computation of (𝑤 ∙ 𝑧 + 𝑥 ∙ 𝑦) can be done as,
𝒓= 𝒘+𝒙 × 𝒚+𝒛 =𝒘∙𝒚+ 𝒘∙𝒛+𝒙∙𝒚 +𝒙∙𝒛

 Only one multiplication is required instead of two.

Additional terms

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 45

Multiplying Large Integers – Example 1
𝟏𝟎𝟒 𝒘 ∙ 𝒚 + 𝟏𝟎𝟐 𝒘 ∙ 𝒛 + 𝒙 ∙ 𝒚 + 𝒙 ∙ 𝒛 𝑤 = 09
𝑥 = 81
 Now we can compute the required product as follows: 𝑦 = 12
𝑧 = 34
𝒑 = 𝒘 ∙ 𝒚 = 𝟎𝟗 ∙ 𝟏𝟐 = 𝟏𝟎𝟖
𝒒 = 𝒙 ∙ 𝒛 = 𝟖𝟏 ∙ 𝟑𝟒 = 𝟐𝟕𝟓𝟒
𝒓 = 𝒘 + 𝒙 × 𝒚 + 𝒛 = 𝟗𝟎 ∙ 𝟒𝟔 = 𝟒𝟏𝟒𝟎

𝒓= 𝒘+𝒙 × 𝒚+𝒛 =𝒘∙𝒚+ 𝒘∙𝒛+𝒙∙𝒚 +𝒙∙𝒛

981 × 1234 = 104𝑝 + 102 (𝑟 − 𝑝 − 𝑞) + 𝑞

= 1080000 + 127800 + 2754
= 1210554.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 46

Multiplying Large Integers – Analysis
 981 × 1234 can be reduced to three multiplications of two-figure numbers (09∙12, 81∙34 𝑎𝑛𝑑
90∙46) together with a certain number of shifts, additions and subtractions.
 Reducing four multiplications to three will enable us to cut 25% of the computing time required
for large multiplications.
 We obtain an algorithm that can multiply two 𝑛-figure numbers in a time,
𝑻(𝒏)= 𝟑𝒕 (𝒏/𝟐) + 𝒈(𝒏), 𝑻(𝒏) = 𝒂𝑻(𝒏/𝒃) + 𝒇(𝒏)
 Solving it gives,
𝑻 𝒏 ∈ 𝜽 𝒏𝒍𝒈𝟑 | 𝒏 𝒊𝒔 𝒂 𝒑𝒐𝒘𝒆𝒓 𝒐𝒇 𝟐

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 47

Multiplying Large Integers – Example 2
 Example: Multiply 𝟖𝟏𝟏𝟒 with 𝟕𝟔𝟐𝟐 using divide & conquer method.
 Solution using D&C

Step 1: 𝒘 = 𝟖𝟏 𝒙 = 𝟏𝟒 𝒚 = 𝟕𝟔 𝒛 = 𝟐𝟐

Step 2: Calculate 𝑝, 𝑞 and 𝑟

𝑝 = 𝑤 ∙ 𝑦 = 81 ∙ 76 = 6156
𝑞 = 𝑥 ∙ 𝑧 = 14 ∙ 22 = 308
𝑟 = (𝑤 + 𝑥) ∙ (𝑦 + 𝑧) = 95 ∙ 98 = 9310
8114 × 7622 = 𝟏𝟎𝟒𝒑 + 𝟏𝟎𝟐 (𝒓 − 𝒑 − 𝒒) + 𝒒
= 61560000 + 284600 + 308
= 61844908

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 48

Merge Sort
Introduction
 Merge Sort is an example of divide and conquer algorithm.
 It is based on the idea of breaking down a list into several sub-lists until each sub list consists
of a single element.
 Merging those sub lists in a manner that results into a sorted list.
 Procedure
 Divide the unsorted list into N sub lists, each containing 1 element
 Take adjacent pairs of two singleton lists and merge them to form a list of 2 elements. N will now convert
into N/2 lists of size 2
 Repeat the process till a single sorted list of all the elements is obtained

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 50

Merge Sort – Example

Unsorted Array
724 521 2 98 529 31 189 451
1 2 3 4 5 6 7 8

Step 1: Split the selected array

1 2 3 4 5 6 7 8
724 521 2 98 529 31 189 451

724 521 2 98 529 31 189 451

1 2 3 4 1 2 3 4

#3150703 (ADA)  Unit 3 – Divide and Conquer Algorithms 51

Merge Sort – Example
Select the left subarray and Split Select the right subarray and Split
1 2 3 4 1 2 3 4
724 521 2 98 529 31 189 451

1 2 1 2 Split 1 2 1 2
724 521 2 98 529 31 189 451

1 1 1 1 1 1 1 1
724 521 2 98 529 31 189 451

521 724 2 98 31 529 189 451

Merge
2 98 521 724 31 189 451 529

2 31 98 189 451 521 529 724

#3150703 (ADA)  Unit 3 – Divide and Conquer Algorithms 52
Merge Sort – Algorithm
Procedure: mergesort(T[1,…,n]) Procedure:
merge(U[1,…,m+1],V[1,…,n+1],T[1,…,m+n])
if n is sufficiently small then
insert(T) i ← 1;
else j ← 1;
array U[1,…,1+n/2],V[1,…,1+n/2] U[m+1], V[n+1] ← ∞;
U[1,…,n/2] ← T[1,…,n/2] for k ← 1 to m + n do
V[1,…,n/2] ← T[n/2+1,…,n] if U[i] < V[j]
mergesort(U[1,…,n/2]) then T[k] ← U[i];
mergesort(V[1,…,n/2]) i ← i + 1;
merge(U, V, T) else T[k] ← V[j];
j ← j + 1;

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 53

Merge Sort - Analysis
 Let 𝑻(𝒏) be the time taken by this algorithm to sort an array of 𝑛 elements.
 Separating 𝑇 into 𝑈 & 𝑉 takes linear time; 𝑚𝑒𝑟𝑔𝑒(𝑈, 𝑉, 𝑇) also takes linear time.

𝑇(𝑛) = 𝑇(𝑛/2) + 𝑇(𝑛/2) + 𝑔(𝑛) where 𝑔(𝑛) ∈ θ(𝑛).

𝑇(𝑛) = 2𝑡(𝑛/2) + θ(𝑛) 𝒕 𝒏 = 𝒍𝒕 𝒏/𝒃 + 𝐠 𝒏
 Applying the general case, 𝑙 = 2, 𝑏 = 2, 𝑘 = 1

 Since 𝑙 = 𝑏𝑘 the second case applies so, 𝑡(𝑛) ∈ θ(𝑛𝑙𝑜𝑔𝑛).

 Time complexity of merge sort is 𝛉(𝒏𝒍𝒐𝒈𝒏). 𝜽 𝒏𝒌 𝒊𝒇 𝒍 < 𝒃𝒌
𝒕 𝒏 = 𝜽 𝒏𝒌 𝒍𝒐𝒈𝒏 𝒊𝒇 𝒍 = 𝒃𝒌
𝜽 𝒏𝒍𝒐𝒈𝒃 𝒍 𝒊𝒇 𝒍 > 𝒃𝒌

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 54

Strassen’s Algorithm for Matrix
Multiplication
Matrix Multiplication
 Multiply following two matrices. Count how many scalar multiplications are required.
1 3 6 8
∙
7 5 4 2

1×6+3×4 1×8+3×2
𝑎𝑛𝑠𝑤𝑒𝑟 =
7×6+5×4 7×8+5×2

 To multiply 2 × 2 matrices, total 8 (23) scalar multiplications are required.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 56

Matrix Multiplication
 In general, 𝐴 and 𝐵 are two 2 × 2 matrices to be multiplied.
𝐴11 𝐴12 𝐵11 𝐵12
𝐴= and 𝐵 =
𝐴21 𝐴21 𝐵21 𝐵22

𝐶11 𝐶12 𝐴11 𝐴12 𝐵11 𝐵12

𝐶= = ∙
𝐶21 𝐶22 𝐴21 𝐴22 𝐵21 𝐵22

𝐶11 = 𝐴11 ∙ 𝐵11 + 𝐴12 ∙ 𝐵21

𝐶12 = 𝐴11 ∙ 𝐵12 + 𝐴12 ∙ 𝐵22
𝐶21 = 𝐴21 ∙ 𝐵11 + 𝐴22 ∙ 𝐵21
𝐶22 = 𝐴21 ∙ 𝐵12 + 𝐴22 ∙ 𝐵22
 Computing each entry in the product takes 𝒏 multiplications and there are 𝒏𝟐 entries for a total
of 𝑶(𝒏𝟑 ).

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 57

Strassen’s Algorithm for Matrix Multiplication
 Consider the problem of multiplying two 𝑛 × 𝑛 matrices.
 Strassen’s devised a better method which has the same basic method as the multiplication of
long integers.
 The main idea is to save one multiplication on a small problem and then use recursion.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 58

Strassen’s Algorithm for Matrix Multiplication
𝐴11 𝐴12 𝐵 𝐵12
𝐴= and 𝐵 = 11
Step 1 Step 2 Step 3 𝐴21 𝐴21 𝐵21 𝐵22

𝑆1 = 𝐵12 − 𝐵22 𝑃1 = 𝐴11 ∙ 𝑆1

Final Answer:
𝑆2 = 𝐴11 + 𝐴12 𝑃2 = 𝑆2 ∙ 𝐵22
𝐶11 𝐶12
𝑃3 = 𝑆3 ∙ 𝐵11 𝐶=
𝑆3 = 𝐴21 + 𝐴22 𝐶21 𝐶22
𝑆4 = 𝐵21 − 𝐵11 𝑃4 = 𝐴22 ∙ 𝑆4 Where,
𝑆5 = 𝐴11 + 𝐴22 𝑃5 = 𝑆5 ∙ 𝑆6 𝐶11 = 𝑃5 + 𝑃4 − 𝑃2 + 𝑃6
𝑆6 = 𝐵11 + 𝐵22 𝑃6 = 𝑆7 ∙ 𝑆8 𝐶12 = 𝑃1 + 𝑃2
𝑆7 = 𝐴12 − 𝐴22 𝑃7 = 𝑆9 ∙ 𝑆10 𝐶21 = 𝑃3 + 𝑃4
𝑆8 = 𝐵21 + 𝐵22 All above 𝐶22 = 𝑃5 + 𝑃1 − 𝑃3 − 𝑃7
𝑆9 = 𝐴11 − 𝐴21 operations No multiplication is
involve only one required here.
𝑆10 = 𝐵11 + 𝐵12 multiplication.
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 59
Strassen’s Algorithm - Analysis
 It is therefore possible to multiply two 2 × 2 matrices using only seven scalar multiplications.
 Let 𝑡(𝑛) be the time needed to multiply two 𝑛 × 𝑛 matrices by recursive use of equations.
𝒕(𝒏) = 𝟕𝒕(𝒏/𝟐) + 𝒈(𝒏) 𝒕 𝒏 = 𝒍𝒕 𝒏/𝒃 + 𝐠 𝒏
Where 𝑔(𝑛) ∈ 𝑂(𝑛2).

 The general equation applies with 𝑙 = 7, 𝑏 = 2 and 𝑘 = 2.

 Since 𝑙 > 𝑏 𝑘 , the third case applies and 𝑡 𝑛 ∈ 𝑂 𝑛𝑙𝑔7 .

 Since 𝑙𝑔7 > 2.81, it is possible to multiply two 𝑛 × 𝑛 matrices in a time 𝑶(𝒏𝟐.𝟖𝟏 ).

𝜽 𝒏𝒌 𝒊𝒇 𝒍 < 𝒃𝒌
𝒕 𝒏 = 𝜽 𝒏𝒌 𝒍𝒐𝒈𝒏 𝒊𝒇 𝒍 = 𝒃𝒌
𝜽 𝒏𝒍𝒐𝒈𝒃 𝒍 𝒊𝒇 𝒍 > 𝒃𝒌
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 60
Quick Sort
Introduction
 Quick sort chooses the first element as a pivot element, a lower bound is the first index and an
upper bound is the last index.
 The array is then partitioned on either side of the pivot.
 Elements are moved so that, those greater than the pivot are shifted to its right whereas the
others are shifted to its left.
 Each Partition is internally sorted recursively.

Pivot
Element

0 1 2 3 4 5 6 7 8 9
42 23 74 11 65 58 94 36 99 87

LB UB

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 62

Quick Sort - Example
Procedure pivot(T[i,…,j]; var l) 0 1 2 3 4 5 6 7 8 9
p ← T[i] 42 23 74 11 65 58 94 36 99 87
k ← i; l ← j+1 k l
Repeat
k ← k+1 until T[k] > p or k ≥ j Swap
Repeat 42 23 36
74 11 65 58 94 74
36 99 87
l ← l-1 until T[l] ≤ p k l
While k < l do
Swap
Swap T[k] and T[l]
Repeat k ← k+1 until 11
42 23 36 42
11 65 58 94 74 99 87
T[k] > p k l
Repeat l ← l-1 until
T[l] ≤ p LB = 0, UB = 9
Swap T[i] and T[l] p = 42
k = 0, l = 10

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 63

Quick Sort - Example
Procedure pivot(T[i,…,j]; var l) 0 1 2 3 4 5 6 7 8 9
p ← T[i] 11 23 36 42 65 58 94 74 99 87
k ← i; l ← j+1 LB UB
Repeat
k ← k+1 until T[k] > p or k ≥ j 11 23 36
Repeat
k l
l ← l-1 until T[l] ≤ p
While k < l do LB UB
Swap T[k] and T[l] 11 23 36 42 65 58 94 74 99 87
Repeat k ← k+1 until
T[k] > p
Repeat l ← l-1 until
23 36
T[l] ≤ p k l
Swap T[i] and T[l]
11 23 36 42 65 58 94 74 99 87

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 64

Quick Sort - Example
LB UB
Procedure pivot(T[i,…,j]; var l) 0 1 2 3 4 5 6 7 8 9
p ← T[i] 11 23 36 42 65 58 94 74 99 87
k ← i; l ← j+1
Swap
Repeat
k ← k+1 until T[k] > p or k ≥ j 65 65
58 58 94 74 99 87
Repeat
k l
l ← l-1 until T[l] ≤ p
While k < l do
Swap T[k] and T[l] 58 65 94 74 99 87
Repeat k ← k+1 until
T[k] > p
Repeat l ← l-1 until LB UB
T[l] ≤ p 11 23 36 42 58 65 94 74 99 87
Swap T[i] and T[l]

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 65

Quick Sort - Example
LB UB
Procedure pivot(T[i,…,j]; var l) Swap

p ← T[i] 94 74 99
87 87
99
k ← i; l ← j+1 k l
Repeat
Swap
k ← k+1 until T[k] > p or k ≥ j
Repeat
87
94 74 94
87 99
l ← l-1 until T[l] ≤ p k l
While k < l do LB UB
Swap T[k] and T[l] Swap
Repeat k ← k+1 until 74 87
87 74 94 99
T[k] > p
Repeat l ← l-1 until k l
T[l] ≤ p 11 23 36 42 58 65 74 87 94 99
Swap T[i] and T[l]

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 66

Quick Sort - Algorithm
Procedure: quicksort(T[i,…,j]) Procedure: pivot(T[i,…,j]; var l)
{Sorts subarray T[i,…,j] into p ← T[i]
ascending order}
k ← i
if j – i is sufficiently small
then insert (T[i,…,j]) l ← j + 1
else repeat k ← k+1 until T[k] > p or k ≥ j
pivot(T[i,…,j],l) repeat l ← l-1 until T[l] ≤ p
quicksort(T[i,…,l - 1]) while k < l do
quicksort(T[l+1,…,j] Swap T[k] and T[l]
Repeat k ← k+1 until T[k] > p
Repeat l ← l-1 until T[l] ≤ p
Swap T[i] and T[l]

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 67

Quick Sort Algorithm – Analysis
1. Worst Case
 Running time depends on which element is chosen as key or pivot element.
 The worst case behavior for quick sort occurs when the array is partitioned into one sub-array with 𝒏 − 𝟏
elements and the other with 𝟎 element.
 In this case, the recurrence will be,
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑇(0) + 𝜃(𝑛)
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝜃(𝑛)
𝑻(𝒏) = 𝜽(𝒏𝟐)
2. Best Case
 Occurs when partition produces sub-problems each of size n/2.
 Recurrence equation:
𝑇(𝑛) = 2𝑇(𝑛/2) + θ(𝑛)
𝑙 = 2, 𝑏 = 2, 𝑘 = 1, 𝑠𝑜 𝑙 = 𝑏𝑘
𝑻(𝒏) = 𝜽(𝒏𝒍𝒐𝒈𝒏)

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 68

Quick Sort Algorithm – Analysis
3. Average Case
 Average case running time is much closer to the best case.
 If suppose the partitioning algorithm produces a 9:1 proportional split the recurrence will be,
𝑇(𝑛) = 𝑇(9𝑛/10) + 𝑇(𝑛/10) + θ(𝑛)
𝑻(𝒏) = 𝜽(𝒏𝒍𝒐𝒈𝒏)

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 69

Quick Sort - Examples
 Sort the following array in ascending order using quick sort algorithm.
1. 5, 3, 8, 9, 1, 7, 0, 2, 6, 4
2. 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9
3. 9, 7, 5, 11, 12, 2, 14, 3, 10, 6

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 70

Exponentiation
Exponentiation - Sequential
 Let 𝑎 and 𝑛 be two integers. We wish to compute the exponentiation 𝒙 = 𝒂𝒏 .
 Algorithm using Sequential Approach:

function exposeq(a, n)
r ← a
for i ← 1 to n - 1 do
r ← a * r
return r

 This algorithm takes a time in 𝜽(𝒏) since the instruction 𝒓 = 𝒂 ∗ 𝒓 is executed exactly 𝒏 −
𝟏 times, provided the multiplications are counted as elementary operations.

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 72

Exponentiation - Sequential
 But to handle larger operands, we must consider the time required for each multiplication.
 Let 𝒎 is the size of operand 𝒂.
 Therefore, the multiplication performed the 𝒊𝒕𝒉 time round the loop concerns an integer of size
𝒎 and an integer whose size is between 𝒊𝒎 − 𝒊 + 𝟏 and 𝒊𝒎, which takes a time between

𝑀(𝑚, 𝑖𝑚 − 𝑖 + 1) and 𝑀(𝑚, 𝑖𝑚)

𝑎 = 5 𝑠𝑜 𝑚 = 1 and 𝑛 = 25 and suppose 𝑖 = 10

The body of loop executes 10𝑡ℎ time as,
𝒓=𝒂 ∗ 𝒓
here 9 times multiplication is already done so 𝒓 = 𝟓𝟗 = 1953125
The size of 𝑟 in the 10th iteration will be between 𝑖𝑚 − 𝑖 + 1 𝑡𝑜 𝑖𝑚, i.e.,
between 𝟏 𝒕𝒐 𝟏𝟎 10-10+1 10

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 73

Exponentiation - Sequential
 The total time 𝑇(𝑚, 𝑛) spent multiplying when computing an with exposeq is therefore,
𝑛−1 𝑛−1

෍ 𝑀 𝑚, 𝑖𝑚 − 1 + 1 ≤ 𝑇 𝑚, 𝑛 ≤ ෍ 𝑀 𝑚, 𝑖𝑚
𝑖=1 𝑖=1
𝑛−1 𝑛−1

𝑇 𝑚, 𝑛 ≤ ෍ 𝑀 𝑚, 𝑖𝑚 ≤ ෍ 𝑐𝑚 𝑖𝑚
𝑖=1 𝑖=1
𝑛−1

𝑐𝑚2 ෍ 𝑖 ≤ 𝑐𝑚2 𝑛2 = 𝜽 𝒎𝟐 𝒏𝟐
𝑖=1

 If we use the divide-and-conquer multiplication algorithm,

𝑻(𝒎, 𝒏) ∈ 𝜽(𝒎𝒍𝒈𝟑 𝒏𝟐)

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 74

Exponentiation – D & C
 Suppose, we want to compute 𝒂𝟏𝟎
 We can write as,
𝑎10 = (𝑎5)2 = (𝑎. 𝑎4)2 = (𝑎. (𝑎2 )2)2
 In general,
𝑎 𝑖𝑓 𝑛 = 1
2
𝑎 𝑛 = ൞ 𝑎 𝑛 Τ2 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
𝑎 × 𝑎𝑛−1 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
 Algorithm using Divide & Conquer Approach:

function expoDC(a, n)
if n = 1 then return a
if n is even then return [expoDC(a, n/2)]2
return a * expoDC(a, n - 1)
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 75
Exponentiation – D & C
0 𝑖𝑓 𝑛 = 1
Number of operations performed by 𝑁 𝑛 = ቐ𝑁 𝑛Τ2 + 1 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
the algorithm is given by, 𝑁 𝑛 − 1 + 1 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

0 𝑖𝑓 𝑛 = 1
Time taken by the 𝑇 𝑚, 𝑛 = ቐ𝑇 𝑚, 𝑛Τ2 + 𝑀 𝑚 𝑛Τ2, 𝑚 𝑛Τ2 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
𝑇 𝑚, 𝑛 − 1 + 𝑀 𝑚, 𝑛 − 1 𝑚 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
algorithm is given by,
Solving it gives, 𝑻(𝒎, 𝒏) ∈ 𝛉 (𝒎𝒍𝒈𝟑 𝒏𝒍𝒈𝟑 )

function expoDC(a, n)
if n = 1 then return a
if n is even then return [expoDC(a, n/2)]2
return a * expoDC(a, n - 1)
#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 76
Exponentiation – Summary

Multiplication
Classic D&C
exposeq 𝜽 𝒎𝟐 𝒏 𝟐 𝜽 𝒎𝒍𝒈𝟑 𝒏𝟐
expoDC 𝜽 𝒎𝟐 𝒏 𝟐 𝜽 𝒎𝒍𝒈𝟑 𝒏𝒍𝒈𝟑

#3150703 (ADA)  Unit 3 – Divide & Conquer Algorithms 77

Thank You