Divide and Conquer Algorithm Study Notes

By Mukesh Kumar|Updated : December 12th, 2021

Divide and Conquer Design Technique

Divides the problem into smaller but similar subproblems (divide), solve it (conquer), and (combine) these solutions to create a solution to the original problem.

  • Divide: Breaking the problem into several sub-problems that are similar to the original problem but smaller in size,
  • Conquer: Solve the sub-problem recursively (successively and independently). If the subproblems are small enough, solve them in brute force fashion.
  • Combine: Combine these solutions to sub-problems to create a solution to the original problem.

Divide & Conquer Algorithms:

  • Merge sort
  • Quicksort
  • Binary search
  • Multiplication of large integers
  • Matrix multiplication: Strassen’s algorithm
  • Closest-pair algorithms

Divide & Conquer Algorithms can be solved using the master theorem to find the performance of algorithms.


Maximum and Minimum:

MaxMin(i, j, max, min)


if (i=j) then max := min := a[i];

else if (i=j-1) then


if (a[i] < a[j]) then max := a[j]; min := a[i];

else max := a[i]; min := a[j];




mid := ( i + j )/2;

// Solve the sub-problems.

MaxMin( i, mid, max, min );

MaxMin( mid+1, j, max1, min1 );

// Combine the solutions.

if (max < max1) then max := max1;

if (min > min1) then min := min1;



Time Complexity:

T(n) = 0; if n=1

= 1; if n=2

=2T(n/2)=2; if n>2

When n is a power of two, n = 2k, for some positive integer k, then

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

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

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

= 2k-1 T(2) + ∑(1≤i≤k-1) 2k

= 2k-1 + 2k – 2

= 3n/2 – 2 = O(n)

Matrix Multiplication:

Simple approach of multiplication:

The product of two n × n matrices X and Y is a third n × n matrix Z = XY , with (i, j)th entry:

  • Input: X, Y: Array(1 ... n) of number
  • Output: Z: Array(1 ... n) := X x Y
  • Obvious algorithm: Z has n2 entries, each of which multiples n pairs
    • Zij=∑XikYkj
  • Break X into X11, X12, X21, X22
  • Break Y into Y11, Y12, Y21, Y22
  • Break Z into Z11, Z12, Z21, Z22
  • Let Z = product of two n/2 by n/2 arrays


  • T(n)=Θ(1)+8T(n/2)+Θ(n2)
    • Θ(1) time to partition matrices
    • 8 Multiplications of arrays of size n/2n/2
    • Θ(n2) time to add n×n matrices
  • T(n)= Θ(n3) by master method

Strassen's Algorithm:

Matrix multiplication is particularly easy to break into subproblems, because it can be performed block wise. Here divide X into four n/2 × n/2 blocks, and also Y:

Therefore, the product of X and Y is as follows:

  • Uses 7 rather than 8 multiplications of n/2 by n/2 arrays
  • Has more additions and subtractions of n/2 by n/2 arrays

  • T(n)=7T(n/2)+Θ(n2) if n>1
  • Solution (by Master Method): T(n)=Θ(n log 7) =Θ(n2.81)
  • Note: There are other matrix multiplication algorithms which can run even faster with T(n)=O(n2.38)

Maximal Subarray:

Divide and conquer approach to find the maximal subarray:

maxsub(int[] S; low, high: int)
if low = high then return (low, high, S(low)); // return (lowIndex, highIndex, sum)
else mid = (low + high) / 2 ;
(llow, lhigh, lsum) = maxsub(S, low, mid) ;
(rlow, rhigh, rsum) = maxsub(S, mid+1, high) ;
(mlow, mhigh, msum) = middlemaxsub(S, low, mid, high) ;
end if;
return triple with highest sum
end maxsub
middlemaxsub(int[] S; low, high, int) return (lowIndex, highIndex, sum)
start at mid and find bestleft and leftsum
start at mid and find bestright and rightsum
return (bestleft, bestright, rightsum+leftsum)
end middlemaxsub

Closest Pair Algorithm:

Input: P = {p(1), p(2) ,..., p(n)} where p(i) = ( x(i), y(i) ). A set of n points in the plane.

Output: The distance between the two points that are closest.

Note: The distance DELTA( i, j ) between p(i) and p(j) is defined by the expression:

Square root of { (x(i)-x(j))2 + (y(i)-y(j))2 }

float function closest_pair (P: point set; n: integer )


float DELTA;


if n = 2 then

return distance from p(1) to p(2);


P-LEFT := ( p(1), p(2) ,..., p(n/2) );

P-RIGHT := ( p(n/2+1), p(n/2+2) ,..., p(n) );

DELTA-LEFT := closestpair( P-LEFT, n/2 );

DELTA-RIGHT := closestpair( P-RIGHT, n/2 );


/* Determine whether there are points p(l) in P-LEFT and p(r) in P-RIGHT with

distance( p(l), p(r) ) < DELTA. If there are such points, set DELTA to be the smallest


return DELTA;

end if;

end closest_pair;

The section between the two comment lines is the `combine' stage of the Divide-and-Conquer algorithm.

If there are points p(l) and p(r) whose distance apart is less than DELTA then it must be the case that

  • The x-coordinates of p(l) and p(r) differ by at most DELTA.
  • The y-coordinates of p(l) and p(r) differ by at most DELTA.

Integer Multiplication:

Multiplying two n-bit integers algorithm using divide and conquer approach is given below:



Worst-case running time

Best-case running time

Average-case running time

Selection sort

Θ (n2)

Θ (n2)

Θ (n2)

Insertion sort

Θ (n2)

Θ (n)

Θ (n2)

Merge sort

Θ (n log n)

Θ (n log n)

Θ (n log n)


Θ (n2)

Θ (n log n)

Θ (n log n)

Strassen’s Matrix Multiplication




Matrix Multiplication




Integer Multiplication




Closest Pair

Θ (n log n)

Θ (n log n)

Θ (n log n)

Binary Search

Θ(log n)

Θ(log n)

Θ(log n)

Maximum and Minimum




Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link:


write a comment
Load Previous Comments
Prashant Dubey
i think the best case tc of bubble sort is O(n) because when there is already sorted list is present it perform only one step in O(n) time
Tanuj Pandey

Tanuj PandeyJul 29, 2017

@Mallesham Devasane sir i need notes on cookies🙏
Deepali Joshi
Sir pls tell how to remember master method by some example
Bhoomi Prajapati
can you please provide download option of this notes
Vishal Upadhayay
Awesome notes thanks a lot. Best thing it contain recursive equation of all algorithms
Arun Karan

Arun KaranApr 17, 2019

Here are the update to all web users online just need to know
how to fix connections to bluetooth audio devices and wireless displays in windows 10 and access the all setting of device.
Raghav Sharma
Is there any link where i can get some good quality notes for gate CS all subjects. Thanks in advance.
Khushboo Kinner

Khushboo KinnerAug 6, 2020

This comment is hidden because it was marked spam.

Follow us for latest updates