FAQ: Linear Search: Conceptual - Worst Case Performance

In one of the worst cases, the target value is found. Is this case more efficient than the second case because it was able to find the target value in the list? Leave your thoughts on this post in the forum and then click ‘Next’ to move onto the next exercise.

As I see it, in both cases you would have to compare all the records with your desired target record. In the more optimistic scenario, you would find that record at the latest comparison (let’s say the 100th comparison). In the less optimistic scenario, you would conclude at the 100th comparison that the record is not in the boxes. In other words, non of the two scenarios is more efficient as 100 comparisons were made.

In both cases the search had to be done on the entire set of “data”, so was there any difference in time for doing the search? Worst case O(N) then?

Equally Efficient / Unequally Effective.

O(N) = O(N) / 1 != 0


Both are equally ‘efficient’.