297 views

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

edited | 297 views

Complexity of the algorithm is O(n) and is irrespective of the success of if case as both if as well as else are O(1) operations.
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$