The Gateway to Computer Science Excellence
+5 votes

Simple linear search to find max min algo

   for i=2 to n do
     if a[i]>max then
     else if a[i]<min then 

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

in Algorithms by
edited by | 423 views

1 Answer

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

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



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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,471 answers
95,278 users