The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
308 views

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

asked in Algorithms by (209 points)
edited by | 308 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$
$=3(n-1)/2$
answered by Veteran (359k 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

40,903 questions
47,558 answers
146,289 comments
62,306 users