# Why is there a 2n+1 comparison for a linear search algorithm?

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;

• Your algorithm has at most $n$ comparisons. As an aside, $O(n+1) = O(n)$ is any function which is bounded by $Cn$, which is presumably not what you meant when writing that the algorithm would make $O(n+1)$ comparisons. Mar 20, 2014 at 4:31
• Right the algorithm would have at most n comparision because the algorithm has O(n+1) comparisons. Mar 20, 2014 at 5:02
• That's not quite correct. If an algorithm has $O(n+1)$ comparisons then it might have more than $n$ comparisons. For example, an algorithm making $10n+17$ comparisons also has $O(n+1)$ comparisons. Also, $O(n+1)$ is the same as $O(n)$. Make sure that you understand the meaning of big O notation. Mar 20, 2014 at 5:04
• the way I understand big O notation informally speaking is when f(x) is less than or equal to g(x). example: n big O n^2, where f(x) is n and g(x) is n^2. Mar 20, 2014 at 5:09
• Your understanding is incomplete, then. I suggest you review the definition of big O. We say that $f(n) = O(g(n))$ if there is some constant $C > 0$ such that for large enough $n$, $f(n) \leq C g(n)$. In your description, you are missing the constant $C$. Mar 20, 2014 at 13:17

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).

• How come statement executes n+1 times. Should it be n times because it is going through the list of size n? How come statement executes n times? Should 1+1+n+(n+1) be 2n+3? Mar 20, 2014 at 5:15
• See statement 2 is executing total n+1 times, result of first n comparison test is true, and then n+1 th test become false then the loop terminates(then not executing statement 3).so statement 3 which is inside the loop executed total n times.And your question is about number of comparison which is total number of execution of statement 2+statement 3. Mar 20, 2014 at 5:22
• is your question about why O(2n+3)=O(n)? Mar 20, 2014 at 5:24
• You had O(2n+1) when you did the first sum. But should it not be O(2n+3) because of the three 1's? Mar 20, 2014 at 5:26
• OK I have edited my answer.now tell me what is your confusion exactly? Mar 20, 2014 at 5:28