Finding Maximum and Minimum2

Finding Example, Theory, Concept, Algorithm

25 December, 2016     

In the last chapter , we have learned the process how to get Minimum and Maximum in an array.

Now see the ALGORITHM: 

          int MaxMin(a,n,max,min)

              {

                   max=min=a[1]

                     for(i=2;i≤n;i++)

                     {

                        If(a[i]>max)

                        max = a[i]

                    else

                         if(a[i]<min)
                         min = a[i]

                    }

            return(max,min);

            }

 Explanation:

• Input = 10,20,30,1,2,3,11,31,21 
•  A is an array and n is number .
• Max is for maximum value and min for minimum value.
• we need exactly n-1 comparisons.
• For this solution we need two values first.
•  Since they both are O(n) and need n-1 comparisons it’s natural to think that combining the two tasks will be O(n) and 2n – 2 comparisons. However we can reduce the number of comparisons!
• Instead of taking only one item from the array and comparing it against the minimum and maximum we can take a pair of items at each step. Thus we can first compare them and then compare the smaller value with the currently smallest value and the greater item with the currently greatest value.
• In the above example , first 10 is max and min value according to algorithm.
• Loop is going from second value to last.
• Like 20 is greater than 10 so new max= value is 20 and loop is going
•  a[i]>max) so   max = a[i] means 20 is updated max value now.
• Next when 30 is comparing with 1 so first if its incorrect then it will move to else part where a[i]= 1 and min value is 10 .
  

• We already initialize in the beginning. Compare  a[i]<min. 1<10 its true so
• Min is a[i] means new min is 1.
• In last it will return you the max and min value.
• This is the way its work.
     
  
     
  
     
  
     
  
  
  

Time Complexity-          

   Best case             n-1  =  Ω(n)

   Worst case        2(n-1) = O(n)

   Average case     1.5(n-1) = θ(n)

See the solution of last example here and  how can get solution  MAX AND MIN

2)    Finding maximum and minimum in given array:-

             
        Let      Input = 22 ,  13 ,  -5 ,  -8  , 15  ,60   ,17  , 31,  47
                   Output =    

                    max=60,min=-8    

Solution:

Let t(n) be the no. of comparisons

          if T(n)=   0   if n=1

              T(n)=   1   if n=2

         
                T(n)=   t(n/2) + t(n/2) +2  if n>2

                 T(n) = 3n-2/2
                 T(n)= O(n)

using DAC and without DAC will take same time so without using DAC is better because Dac approach take more space and  its recursive programming.

Next we will see the solution of Power of an Integer