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 (219 points)
edited by | 346 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 (400k points)
selected by

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
49,443 questions
53,648 answers
70,907 users