The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+4 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


asked in Algorithms by (245 points)
edited by | 259 views

1 Answer

+4 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 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$
answered by Veteran (332k points)
selected by

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

32,545 questions
39,231 answers
36,613 users