[Solved] Time complexity max min [closed]

by


The average case complexity for both cases is O(n). if k is the number of times the first if fails, then the number of comparisons is 2*n – 2 – k.

maxmin(a,n,max,min){
   max=min=a[1];
   for i=2 to n do{ // goes through the loop n-1 times
      if a[i]>max then max:=a[i]; // out of n-1 times succeeds k times and fails n-1-k times
      else if a[i]<min then min:=a[i]; // runs this n-1-k times
   }
}

n-1 + n-1-k -> 2*n – 2 – k

3

solved Time complexity max min [closed]