[need @arjun sir to verify it ]
We are requested to find the MAX and MIN of the array of $n$ elements . This can be done as follws
Non Divide And Conquer
Max_Min(A,n,max,min)
max=min=a[i]
for i-> 2 to n
{
if A[i] > max // First Comparision
max=A[i]
else if A[i] < min // Seond Comparision
min = A[i]
}
Analysis
Best Case
When input is in increasing order
- First Comparision : $n-1$ time
- Second Comparision: $1$ time
Worst Case
When input is in Decreasing order
- First Comparision : $n-1$ time
- Second Comparision: $n-1$ time
Average Case
When First Comparision fails for half of the input
- First Comparision : $n-1$ time
- Second Comparision: $\frac{n}{2}$ time
Divide And Conquer
Given a function to compute on $n$ inputs the divide-and-conquer strategy suggest splitting the inputs into $k$ distinct subsets, $1 < K \leq n$, yielding $k$ sub problems. These Sub problems must be solved, and then a method must be found to combine sub solutions into a solution of the whole.
Defining the Termination condition 'SMALL' of the problem , When $n \leq 2$. In this case, the maximum and minimum are $a[i] \ \text{if} \ n = 1$ . If $n = 2$, the problem can be solved by making one comparison.
How can we Combine The Subproblem ? If $\text{MAX(A)}$ and $\text{MIN(P)}$ are the maximum and minimum of the elements of A, then $\text{MAX(A)}$ is the larger of $\text{MAX(A1)}$ and $\text{MAX(A2)}$ Similarly for $\text{MIN(A)}$
MaxMin(i, j, max, min)
// a[1:n] is a global array. Parameters i and j are integers,
// 1≤i≤j≤n. The effect is to set max and min to the largest and
// smallest values in a[i:j].
{
if (i=j) then max := min := a[i]; //Small(P)
else if (i=j-1) then // Another case of Small(P)
{
if (a[i] < a[j]) then max := a[j]; min := a[i];
else max := a[i]; min := a[j];
}
else
{
// if P is not small, divide P into sub-problems.
// Find where to split the set.
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;
}
}
Analysis
Time Complexity
$T(n) =\begin{Bmatrix} 0 & n=1\\ 1 & n=2\\ 2T(\frac{n}{2})+2& n>2 \end{Bmatrix}$
Using Master Theorem Case 1 follows . Hence $T(n)$ is $\Theta(n)$
Solution
$\begin{align*} \\ T(n)&=2T(\frac{n}{2})+2\\ &=4T(\frac{n}{4})+2^{2}+2 \\ & ... \\ & = 2^{k}T(\frac{n}{2^{k}})+\sum_{i=1}^{k}2^{i} & (\text{where}\sum_{i=1}^{k}2^{i}=2^{k+1}-2)\\ &=2^{k}T(\frac{n}{2^{k}})+2^{k+1}-2 & ( \text{where,} \ k=(\log n) -1) \\ &=2^{(\log n) -1}T(1)+2^{\log n} -2 \\ &=\frac{n}{2}+n-2 \\ &=\frac{3n}{2}-2 \end{align*}$
For Input Class : Numbers in Increasing Order Non-Divide And Conquer Strategy Perform Better than Divide And Conquer
Space Complexity
$S(n) = n+ \log n + c $ Where $n$ is the input size and $\log n$ is the size of the stack . Hence the space complexity is $O(\log n)$
Example
Consider the array
$A[] = \begin{Bmatrix}
1 &2 &3 &4 & 5 &6 &7 &8 &9 \\
22 & 13 & -5 &-8 &15 &60 &17 &31 &47
\end{Bmatrix}$
Video Example : https://www.youtube.com/watch?v=EHRL2LbS5LU
References
- https://www.youtube.com/watch?v=lEvzwEcjQ54&feature=youtu.be&t=1823
- Cormen
- http://somnathkayal.blogspot.in/2012/08/finding-maximum-and-minimum-using.html
