Time complexity max min

Question

Simple linear search to find max min algo

maxmin(a,n,max,min){
max=min=a[1];
for i=2 to n do{
    if a[i]>max then max:=a[i];
    else if a[i]<min then min:=a[i];
}
}

1.Average case complexity of the above algo given that the first if conditions fails for n/2 elments 2.Average case complexity of the above algo if the first ccondition fails 1/2 times plz xplain

Answer 1

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