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 elements

2.Average case complexity of the above algo if the first condition fails 1/2 times

plz xplain

Answer 1

Complexity of the algorithm is $O(n)$ and is irrespective of the success of if case as both if as well as else is $O(1)$ operation.
If you say exactly, the complexity in terms of comparisons will be

1. $n-n/2-1$ (number of elements for which first if succeeds) $+ 2 \times (n/2) $ (number of elements for which first if fails)

$= 3n/2 -1$

2. $ (n-1)/2 + 2\times (n-1)/2$
$=3(n-1)/2$

Comments

@Arjun Sir

$2\times (n/2)$(number of elements for which first if fails)

why we need to multiplied by $2$ when first 'if' fails? 

---

else case comparison also needs to be counted.

PS: "need to multiply"

---

ok,

but see there are total n elements in for loop. right??

Now, $\frac{n}{2}$ succeds in "first if block"

Then only $\frac{n}{2}$ elements remain.

and these element is in "second if o else if block". Now, how any other elenent exists for this loop or where r u getting "else block " again??

Am I missing something??