Finding minimum and maximum

      No Comments on Finding minimum and maximum

Finding minimum and maximum using divide and conquer

Finding minimum and maximum

Problem statement

Input: Given an array of n elements.
Output: Return maximum and minimum element.

Approach 1: without using divide and conquer

Example:

Input: A [ 10 20 30 56 27 5 14 19 23 0 67]
Output: maximum=67
        minimum=0

This problem can be solved by initializing max and min element as the first and running a for loop
from second index of the array comparing each element with the initialized value. If the value at current index is less than min, update min else if the value is greater than max, update max.
Algorithm:

 1. Initialize max and min =A[1]
 2. for(int i=2;i<=n;i++)
 3.  if (A[i]>max)
       then set max:= A[i]
     else if (A[i]<min)
       then set min:=A[i]
 4. return (max,min)

Time Complexity:

Analyzing from pseudo code:-
 st_min_max(A,n)
 { 
   max=min=A[1];   -----> O(1)
   for(int i=2;i<=n;i++)  ------->  //loops runs n-1 times, each statement takes constant time
   {
      if(A[i]>max)   
          max=A[i];
      else if(A[i]<min)
          min=A[i]
   }
   return(max,min)  -------> O(1)
 }

In best case: number of comparisons will be n-1, as the first statement will evaluate to true always.
In worst case: number of comparisons will be 2(n-1), as both comparisons will be done.
In average case: number of comparisons will be between 2(n-1) and n-1.
Time complexity can be given by TC=O(1)+2(n-1)
Therefore ,time complexity is O(n)

Space complexity:

Space complexity = input + extra (auxiliary space)
                 = 2*n (array size) + variables O(1)
                 = O(n)

Approach 2: using divide and conquer

By using divide and conquer, we use a recursive relation which breaks the problem from middle element into two equal parts.We solve the problem recursively. Note: Each recursive function uses stack.
Algorithm:

max_min(A, i, j, max, min)
{
   if(i==j)  -----------> 0 comparisons
   {
     max=min=A[i];
     return (max,min);
    }
    if(i=j-1)
    {
       if(A[i]>A[j])   -------------> 1 comparisons
       { max=A[i];
         min=A[j]; }
       else
       { max=A[j];
         min=A[i]; }
   }
   else
  {
    mid=(i+j)/2; ----> O(1)
    (max1,min1)=max_min(A, i, mid, max, min);  --->T(n/2)  // if T(n) is complexity for n elements
    (max2,min2)=max_min(A, mid+1, j, max. min); ---->T(n/2)
     if(max1>max2)  ---> 1 comparisons
        max=max1;
     else
        max=max2;
     if(min1>min2)  ---> 2 comparisons
        min=min2;
     else
       min=min1;
   }
    return(max,min);
}      

Time complexity is determined for else part of the code. The initial conditions in if are called termination conditions and do not determine complexity. Referring to above code:
Time complexity :

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

 Solving relation
  T(n)=2*T(n/2)+2
      =2[ 2T(n/2^2) +2] +2
      =2^2*T(n/2^2) + 2^2 +2
        |
        |  k times
        |
      =2^kT(n/2^k) + 2^(k-1)+ 2^(k-2).....+2
      Assuming n/2^k=1 we get k=logn or 2^k=n
      =2^kT(1) + 2(2^k-1)/(2-1)
      =n + n
      =O(n)

Space complexity:

  SC=input + extra space
    =2n + logn (stack used for recursion)
    =O(n)
  Space used by stack is number of levels or distinct function calls made by program.

Summary
Finding minimum and maximum
Article Name
Finding minimum and maximum
Description
Finding minimum and maximum-Problem statement is Input: Given an array of n elements. Output: Return maximum and minimum element. We can solve this problem by using divide and conquer in O(n) time and logn extra space.
Author
Publisher Name
Scanfcode
Publisher Logo

Leave a Reply

Your email address will not be published. Required fields are marked *