423 views

Simple linear search to find max min algo

maxmin(a,n,max,min)
{
max=min=a;
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 | 423 views

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$
by
edited
0

@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?

+1

else case comparison also needs to be counted.

PS: "need to multiply"

0

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??