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

The Gateway to Computer Science Excellence

+5 votes

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

+5 votes

Best answer

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$

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$

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?

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

52,345 questions

60,471 answers

201,800 comments

95,278 users