[Solved]: Why is there a 2n+1 comparison for a linear search algorithm?

Problem Detail: 

Suppose an algorithm goes through a list of n integers and for every iteration of the loop it is needs to check if the current evaluated element of the list is even. If it is even, return the index of the integer that is evaluated as even.

How come the algorithm would have 2n+1 comparison?

I thought linear search would have n comparision because it is going through n elements. +1 comparison for the if statement. So that would make the algorithm O(n+1) comparison, no?. Where did the extra n come from?

Pseudo-code:

procedure last_even_loc(a1,a2,...,an:integers); location = 0; for i = 1 to n      if (a_i = 0) (mod 2) then location = i  return location; 

Asked By : Nicholas

Answered By : tanmoy

procedure last_even_loc(a1,a2,...,an:integers) 1.location = 0; 2.for i = 1 to n 3.    if (a_i = 0) (mod 2) then location = i 4.return location; 

statement 1 is executing only once. statemet 2 is executing total n+1 times. statement 3 is executing total n times. statement 4 is executing only once.

The running time of the algorithm is the sum of running time of all the statements executed.so running time=1+1+n+(n+1)=O(2n+3)=O(n).so there is total n+1+n=2n+1 comparisons(statement 2 and 3).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22849

 Ask a Question

 Download Related Notes/Documents