In the last chapter , we have learned the process how to get Minimum and Maximum in an array.
Now see the ALGORITHM:
max = a[i]
min = a[i]
- 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.
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
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
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