Department of Computer Science and Engineering

Design and Analysis of Algorithms[PCC-CSE-307]

Module-II: Divide and Conquer

Dr. A K Yadav
Associate Professor

Department of Computer Science and Engineering

Indira Gandhi University Meerpur, Rewari, Haryana-122502

September 3, 2025

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 1/26
 Department of Computer Science and Engineering

Contents

Divide and Conquer Technique 3

Merge Sort 4
Quick Sort 9
Heap Sort 12
Randomized Quick Sort 15
Strassen’s algorithm 17
Medians and Order Statistics 24

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 2/26
 Department of Computer Science and Engineering

Divide and Conquer Technique

▶ The divide-and-conquer technique involves taking a large-scale
problem and dividing it into similar sub-problems of a smaller
scale.
▶ Each sub-problem is a non-overlapping sub-problems.
▶ Solve each of these sub-problems recursively.
▶ Generally, a problem is divided into sub problems repeatedly
until the resulting sub-problems are very easy to solve.
▶ This technique can be divided into the following three parts:
▶ Divide: This involves dividing the problem into smaller
sub-problems.
▶ Conquer: Solve sub-problems by calling recursively until
solved.
▶ Combine: Combine the sub-problems to get the final solution
of the whole problem.
Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 3/26
 Department of Computer Science and Engineering

Merge Sort
MERGE-SORT(A, p, r)
1 if p < r
2 q = (p + r )/2
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q+1, r)
5 MERGE(A,p,q,r)
MERGE(A, p, q, r)
6 n1 = q − p + 1
7 n2 = r − q
8 Let L[1..n1 ] and R[1..n2 ] be new arrays
9 for i = 1 to n1
10 L[i] = A[p + i − 1]
11 for j = 1 to n2

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 4/26
 Department of Computer Science and Engineering

12 R[j] = A[q + j]
13 i = 1
14 j = 1
15 for k = p to r
16 if L[i] ≤ R[j]
17 A[k] = L[i]
18 i = i + 1
19 else
20 A[k] = R[j]
21 j = j + 1

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 5/26
 Department of Computer Science and Engineering

Working of Merge

Analysis:

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 6/26
 Department of Computer Science and Engineering

▶ First call of merge-sort will be MERGE-SORT(A, 1, n) for

input size n.
▶ q is half of n,q = n2 in step 2.
▶ Every call of merge-sort divides the size in half and double the
sub-problems.
▶ So there will be only lg n calls of merge-sort and sum of size
of all sub-problems is n
▶ There is only one call for each merge-sort call
▶ So total calls of the merge will be lg n
▶ Step 6 to 8 will be executed lg n times
▶ Step 9 will be executed n1 lg n times
▶ Step 10 will be executed n1 lg n times
▶ Step 11 will be executed n2 lg n times
▶ Step 12 will be executed n2 lg n times
Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 7/26
 Department of Computer Science and Engineering

▶ Total of Step 9 to 12 will be executed 2(n1 + n2 ) lg n times

▶ Step 13 & 14 will be executed lg n times
▶ For each call of lg n step 15 will be executed n lg n times
▶ Step 16 will be executed n lg n times
▶ Every time either step 17 & 18 or step 20 & 21 will be
executed and sum of these will be n lg n.
▶ After adding cost of all these step
T (n) = an lg n + bn + c = O(n lg n)

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 8/26
 Department of Computer Science and Engineering

Quick Sort
QUICK-SORT(A, p, r)
1 if p < r
2 q=PARTITION(A,p,r)
3 QUICK-SORT(A, p, q-1)
4 QUICK-SORT(A, q+1, r)
PARTITION(A, p, r)
5 x = A[r ]
6 i =p
7 for j = p to r − 1
8 if A[j] ≤ x
9 if(i ̸= j) swap(A[i], A[j])
10 i = i + 1
11 swap(A[i], A[r ])

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 9/26
 Department of Computer Science and Engineering

12 return i
Analysis:
▶ The number of calls of PARTITION depends on
QUICK-SORT
▶ The number of calls of QUICK-SORT depends on q
▶ If PARTITION returns q as middle value for every call
▶ Then array will be divided in two half every time
▶ So after lg n times, p = r and process will terminate.
▶ This will be Best Case of the algorithm.
▶ ∴ T (n) = O(n lg n) for best case
▶ But if PARTITION find A[r ] fit at its current location after
checking p to r-1 elements then it return q as an end position
and making partition of size 0 and n − 1.
▶ So every time the array size is reduced by only 1.
Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 10/26
 Department of Computer Science and Engineering

▶ The process will terminate after n operations.

▶ This will be Worst Case of the algorithm and happens when
input is already sorted.
▶ Step 7 will be executed n times for every value of q in step 2.
▶ ∴ T (n) = O(n2 ) for worst case

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 11/26
 Department of Computer Science and Engineering

Heap Sort
▶ Like merge sort but unlike insertion sort, Heap sort running
time is O(nlogn).
▶ Like insertion sort but unlike merge sort, heap sort sorts in
place: only a constant number of array elements are stored
outside the input array at any time.
▶ So heap sort combines the better attributes of the two sorting
algorithms.
QUICK-SORT(A, p, r)
1 if p < r
2 q=PARTITION(A,p,r)
3 QUICK-SORT(A, p, q-1)
4 QUICK-SORT(A, q+1, r)
PARTITION(A, p, r)

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 12/26
 Department of Computer Science and Engineering

5 x = A[r ]
6 i =p
7 for j = p to r − 1
8 if A[j] ≤ x
9 if(i ̸= j) swap(A[i], A[j])
10 i = i + 1
11 swap(A[i], A[r ])
12 return i
Analysis:
▶ The number of calls of PARTITION depends on
QUICK-SORT
▶ The number of calls of QUICK-SORT depends on q
▶ If PARTITION returns q as middle value for every call
▶ Then array will be divided in two half every time

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 13/26
 Department of Computer Science and Engineering

▶ So after lg n times, p = r and process will terminate.

▶ This will be Best Case of the algorithm.
▶ ∴ T (n) = O(n lg n) for best case
▶ But if PARTITION find A[r ] fit at its current location after
checking p to r-1 elements then it return q as an end position
and making partition of size 0 and n − 1.
▶ So every time the array size is reduced by only 1.
▶ The process will terminate after n operations.
▶ This will be Worst Case of the algorithm and happens when
input is already sorted.
▶ Step 7 will be executed n times for every value of q in step 2.
▶ ∴ T (n) = O(n2 ) for worst case

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 14/26
 Department of Computer Science and Engineering

Randomized Quick Sort

▶ To avoid the worst performance of the Quick Sort for sorted
input, we use Randomized Quick Sort.
▶ In this we choose pivot element randomly.
Algorithm:
RANDOMIZED-QUICK-SORT(A, p, r)
1 if p < r
2 q=RANDOMIZED-PARTITION(A,p,r)
3 RANDOMIZED-QUICK-SORT(A, p, q-1)
4 RANDOMIZED-QUICK-SORT(A, q+1, r)
RANDOMIZED-PARTITION(A, p, r)
5 i = Random(p, r )
6 swap(A[i], A[r ])
7 x = A[r ]
Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 15/26
 Department of Computer Science and Engineering

8 i =p
9 for j = p to r − 1
10 if A[j] ≤ x
11 if(i ̸= j) swap(A[i], A[j])
12 i = i + 1
13 swap(A[i], A[r ])
14 return i
This algorithm performs worst case only when Random(p, r ) always
gives the location of the largest/smallest number which is very rare.

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 16/26
 Department of Computer Science and Engineering

Strassen’s algorithm for Matrix Multiplications

▶ if we multiply two matrices Cn×m = An×l Bl×m
▶ Total number of scaler multiplications will be n × l × m
▶ If we take matrices of size n × n where n is power of 2 i.e
n = 2i
▶ Total number of scaler multiplications will be n3
▶ If we divide size by 2 then the matrices will be
!
A11 A12
A=
A21 A22
!
B11 B12
B=
B21 B22
!
C11 C12
C=
C21 C22
Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 17/26
 Department of Computer Science and Engineering

▶
! ! !
C11 C12 A11 A12 B11 B12
=
C21 C22 A21 A22 B21 B22

C11 = A11 .B11 + A12 .B21

C12 = A11 .B12 + A12 .B22

C21 = A21 .B11 + A22 .B21
C22 = A21 .B12 + A22 .B22
▶ So there are 8 multiplication and 4 submissions of size n/2

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 18/26
 Department of Computer Science and Engineering

▶
n
 
T (n) = 8T + 4(n/2)2
2
▶ Solution of the recurrence will be Θ(n3 ) using master theorem.
So no benefit of dividing the main problem in subproblems.
▶ Strassen’s gives 18 sum and 7 products of size n/2 as follows:

S1 = B12 − B22

S2 = A11 + A12
S3 = A21 + A22
S4 = B21 − B11
S5 = A11 + A22

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 19/26
 Department of Computer Science and Engineering

S6 = B11 + B22
S7 = A12 − A22
S8 = B21 + B22
S9 = A11 − A21
S10 = B11 + B12

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 20/26
 Department of Computer Science and Engineering

▶ 7 products will be

P1 = A11 .S1

P2 = S2 .B22
P3 = S3 .B11
P4 = A22 .S4
P5 = S5 .S6
P6 = S7 .S8
P7 = S9 .S10

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 21/26
 Department of Computer Science and Engineering

▶ Now the the matrix will be

C11 = P5 + P4 − P2 + P6

C12 = P1 + P2
C21 = P3 + P4
C22 = P5 + P1 − P3 − P7
▶ There are 7 multiplication and 18 submissions of size n/2
▶
n
 
T (n) = 7T + 18(n/2)2
2

▶ The solution of the recurrence will be Θ(nlg 7 ) using master

theorem which is less then Θ(n3 )

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 22/26
 Department of Computer Science and Engineering

▶ So Strassen’s algorithm is faster then divide and conquer.

▶ Ques.1 Find the product of the following matrices using
Strassen’s algorithm.
! !
1 3 6 8
7 5 4 2

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 23/26
 Department of Computer Science and Engineering

Medians and Order Statistics

▶ The i th Order Statistic of a set of n elements is the i th
smallest element.
▶ The 1st Order Statistic is the minimum of the set.
▶ The nth Order Statistic is the maximum of the set.
▶ Median is the middle element of the set.
▶ If n is odd then unique median will be at (n + 1)/2
▶ If n is even then two median lower and upper will be at n/2
and n/2 + 1 respectively.
▶ So lower median will be at ⌊(n + 1)/2⌋ and upper median
will be at ⌈(n + 1)/2⌉ for both n even or odd.

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 24/26
 Department of Computer Science and Engineering

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 25/26
 Department of Computer Science and Engineering

Thank you
Please send your feedback or any queries to [Link]@[Link]

Module-II: Divide and Conquer Dr. A K Yadav Associate Professor Design and Analysis of Algorithms 26/26