Complexity of the linear search algorithm

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

procedure linear search( $x$: integer, $a_1, a_2, \dots a_n$: distinct integers $i := 1$
while( $i \leq n$ and $x \neq a_i$) $i:=i+1$
if $i \leq n$ then location: $i$
else location:= $0$
return location

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

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

1. Is $i \leq n$?
2. Is $x \neq a_i$?
3. If the answer to both of these is yes, you stay in the loop. From one perspective, that means there’s a third comparison:

4. Are both answers above “yes?”

We hadn’t been including this third comparison in our calculation that, in the worst case, there are $2n+2$ comparisons. If we had, the answer would have been $3n+2$. It’s certainly not wrong to include the third comparison, but it’s not absolutely necessary either and $2n+2$ 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 $2n+2$ and $3n+2$ are $\Theta(n)$. (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.

This entry was posted in Discussion. Bookmark the permalink.

2 Responses to Complexity of the linear search algorithm

1. Donald Young says:

Prof. Poirier,
I have been studying how to read the homework to gauge how many comparisons each
algorithm requires. I don’t get it. If you can offer any help, it would be greatly appreciated. Thank you in advance.
~ Donald ~

• Kate Poirier says:

Hi Donald. We’ll see another example in class tomorrow, so hopefully that’ll help. We can also talk about last week’s two examples either in class or during office hours. In general, if you can write what an algorithm is doing for a small set of inputs…either in plain English or in diagrams…you might be able to understand the counts better. If you think you do have an idea, but it doesn’t match with the answers in the back of the book, try walking us through your count so that we can try to find where you’re going wrong.