  # Divide and Conquer Algorithm Study Notes

By BYJU'S Exam Prep

Updated on: September 25th, 2023 ## 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];

}

else

{

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

Z11=X11×Y11+X12×Y21
Z12=X11×Y12+X12×Y22
Z21=X21×Y11+X22×Y21
Z22=X21×Y12+X22×Y22

• 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-LEFT, DELTA-RIGHT;

float DELTA;

begin

if n = 2 then

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

else

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 );

DELTA := minimum ( DELTA-LEFT, DELTA-RIGHT );

/* 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

distance.*/

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: ## Summary:

 Algorithm 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) Quicksort Θ (n2) Θ (n log n) Θ (n log n) Strassen’s Matrix Multiplication Θ(n2.81) Θ(n2.81) Θ(n2.81) Matrix Multiplication Θ(n2.38) Θ(n2.38) Θ(n2.38) Integer Multiplication Θ(n1.585) Θ(n1.585) Θ(n1.585) Closest Pair Θ (n log n) Θ (n log n) Θ (n log n) Binary Search Θ(log n) Θ(log n) Θ(log n) Maximum and Minimum Θ(n) Θ(n) Θ(n)

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU’S Exam Prep Test Series check the following link: GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com