Max-Min problem is to find a maximum and minimum element from the given array. We can effectively solve it using divide and conquer approach.
In the traditional approach, the maximum and minimum element can be found by comparing each element and updating Max and Min values as and when required. This approach is simple but it does (n – 1) comparisons for finding max and the same number of comparisons for finding the min. It results in a total of 2(n – 1) comparisons. Using a divide and conquer approach, we can reduce the number of comparisons.
Divide and conquer approach for Max. Min problem works in three stages.
- If a1 is the only element in the array, a1 is the maximum and minimum.
- If the array contains only two elements a1 and a2, then the single comparison between two elements can decide the minimum and maximum of them.
- If there are more than two elements, the algorithm divides the array from the middle and creates two subproblems. Both subproblems are treated as an independent problem and the same recursive process is applied to them. This division continues until subproblem size becomes one or two.
After solving two subproblems, their minimum and maximum numbers are compared to build the solution of the large problem. This process continues in a bottom-up fashion to build the solution of a parent problem.
Algorithm for Max-Min Problem
Algorithm DC_MAXMIN (A, low, high) // Description : Find minimum and maximum element from array using divide and conquer approach // Input : Array A of length n, and indices low = 0 and high = n - 1 // Output : (min, max) variables holding minimum and maximum element of array if n == 1 then return (A, A) else if n == 2 then if A < A then return (A, A) else return (A, A) else mid ← (low + high) / 2 [LMin, LMax] = DC_MAXMIN (A, low, mid) [RMin, RMax] = DC_MAXMIN (A, mid + 1, high) if LMax > RMax then // Combine solution max ← LMax else max ← RMax end if LMin < RMin then // Combine solution min ← LMin else min ← RMin end return (min, max) end
The conventional algorithm takes 2(n – 1) comparisons in worst, best and average case.
DC_MAXMIN does two comparisons to determine the minimum and maximum element and creates two problems of size n/2, so the recurrence can be formulated as
T(n) = 0, if n = 1
T(n) = 1, if n = 2
T(n) = 2T(n/2) + 2, if n > 2
Let us solve this equation using interactive approach.
T(n) = 2T(n/2) + 2 … (1)
By substituting n by (n / 2) in Equation (1)
T(n/2) = 2T(n/4) + 2
⇒ T(n) = 2(2T(n/4) + 2) + 2
= 4T(n/4) + 4 + 2 … (2)
By substituting n by n/4 in Equation (1),
T(n/4) = 2T(n/8) + 2
Substitute it in Equation (1),
T(n) = 4[2T(n/8) + 2] + 4 + 2
= 8T(n/8) + 8 + 4 + 2
= 23 T(n/23) + 23 + 22 + 21
After k – 1 iterations
It can be observed that divide and conquer approach does only [(3n/2) – 2] comparisons compared to 2(n – 1) comparisons of the conventional approach.
For any random pattern, this algorithm takes the same number of comparisons.
It can be observed that divide and conquer approach does only comparisons compared to 2(n – 1) comparisons of the conventional approach. For any random pattern, this algorithm takes the same number of comparisons.
Problem: Find max and min from the sequence <33, 11, 44, 55, 66, 22> using divide and conquer approach
During the divide step, the algorithm divides the array until it reaches a size of one or two. Once the array size reaches the base case, we may get the maximum and minimum number from each array recursively. This method is continued until all of the subarrays have been processed. The figure below depicts the complete procedure.
The orange cell represents the stage of stepwise division. In the conquer stage, the smallest element from the parent arrays is placed in the green cell, while the largest element is stored in the blue cell.
Some Popular Problems Solved using Divide and Conquer
- Linear Search
- Binary Search
- Convex Hull
- Max-Min Problem
- Larger Integer Multiplication
- Strassen’s Matrix Multiplication
- Finding Exponent Problem
- Merge Sort
- Quick Sort
Additional Resource: Read for more detail