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?


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;
  • $\begingroup$ 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. $\endgroup$ Commented Mar 20, 2014 at 4:31
  • $\begingroup$ Right the algorithm would have at most n comparision because the algorithm has O(n+1) comparisons. $\endgroup$
    – Nicholas
    Commented Mar 20, 2014 at 5:02
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Mar 20, 2014 at 5:04
  • $\begingroup$ 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. $\endgroup$
    – Nicholas
    Commented Mar 20, 2014 at 5:09
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Mar 20, 2014 at 13:17

1 Answer 1

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

  • $\begingroup$ 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? $\endgroup$
    – Nicholas
    Commented Mar 20, 2014 at 5:15
  • $\begingroup$ 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. $\endgroup$ Commented Mar 20, 2014 at 5:22
  • $\begingroup$ is your question about why O(2n+3)=O(n)? $\endgroup$ Commented Mar 20, 2014 at 5:24
  • $\begingroup$ 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? $\endgroup$
    – Nicholas
    Commented Mar 20, 2014 at 5:26
  • $\begingroup$ OK I have edited my answer.now tell me what is your confusion exactly? $\endgroup$ Commented Mar 20, 2014 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.