# 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. – Yuval Filmus Mar 20 '14 at 4:31
• Right the algorithm would have at most n comparision because the algorithm has O(n+1) comparisons. – Nicholas Mar 20 '14 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. – Yuval Filmus Mar 20 '14 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. – Nicholas Mar 20 '14 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$. – Yuval Filmus Mar 20 '14 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? – Nicholas Mar 20 '14 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. – tanmoy Mar 20 '14 at 5:22
• is your question about why O(2n+3)=O(n)? – tanmoy Mar 20 '14 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? – Nicholas Mar 20 '14 at 5:26
• OK I have edited my answer.now tell me what is your confusion exactly? – tanmoy Mar 20 '14 at 5:28