Complexity of the linear search algorithm

Benjamin asked a great question after class today. The linear search algorithm is:

procedure linear search(: integer, : distinct integers

while( and )
   
if then location:
else location:=
return location

We said that we were usually interested in the worst-case scenario, but the question applies no matter where is on the list.

For each value of (that means for each round in the while loop), there are two comparisons:

1. Is ?
2. Is ?

If the answer to both of these is yes, you stay in the loop. From one perspective, that means there’s a third comparison:

3. Are both answers above “yes?”

We hadn’t been including this third comparison in our calculation that, in the worst case, there are comparisons. If we had, the answer would have been . It’s certainly not wrong to include the third comparison, but it’s not absolutely necessary either and is what I’d expect to see from you. What I told Benjamin is that, if he were to hand in his solution, as long as he described all the comparisons clearly and in full detail (especially the third one, since I wouldn’t be anticipating it…but actually all three since he won’t anticipate what I’m anticipating and what I’m not anticipating), then he’d get full credit.

In practice, this distinction doesn’t really matter. Both functions and are . (If all you’re looking for is the order, you can also safely be sloppy about the constants we discussed at the end of class.) Of course, in this class, you might be asked for the precise count of basic operations as well as the order, so be prepared to explain each step of your count explicitly.