Min Max based on Divide and Conquer
In divide and conquer approach, the problem is divided into smaller but similar sub-problems and then each problem is solved independently. When we keep on dividing the sub problems into even smaller sub-problems, we may reach a stage where no more division is possible. Those smallest possible sub-problem are solved individually and the solution of all sub-problems is finally merged/combined in order to obtain the solution of an original problem.
Divide and Conquer algorithm solves a problem using following three steps.
1. Divide: Break the given problem into subproblems of same type.
2. Conquer: Recursively solve these subproblems
3. Combine: Appropriately combine the answers
In MinMax problem, given a list with n elements i.e a[1:n], we have to find the maximum and minimum value out of the list.
As Divide and Conquer suggests, the list is divided in two half and recursively call MinMax function to get min and max out of left sub list and min1 and max1 from right sub list. final max will be the maximum value out of max and max1 and similarly final min value will be the minimum value out of min and min1. The above is carried out if n is greater than two.
But if n=1 (Small P) i.e. list contains only one value then that value will be min as well as max.
Also when list contains only two elements then with a single comparison, we can get a max and a min value.
The worst case complexity will be 3n/2 - 2 that is O(n).