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

:wink:

Both are equally ‘efficient’.

I really liked everyone’s answer here. If the match occurs at the end of the search, we’ve reached O(N) complexity, so it’s an inefficient search but we’ve got our answer, otherwise, if there’s is no match, it is not only inefficient but we wasted O(N) time, effectively for nothing.

An algorithm is only as efficient as its worst case, both in time complexity and space complexity. A linear search of unsorted, nominal values cannot be made more efficient.

In any way, the linear search still has to go through the list, and hence, the runtime still remains the same :slight_smile:

I think that time compexity of linear search as I know about it for the moment, may depend on how long each element of the list or array is (besides the quantity of the elements). fo example if it’s a text variations, that are different only by endings…
But if we take the same array and choose to find an element that is there on the last position or is absent, the time of search should be the same…What is the triсk? I’m dying of curiosity!

If I go to grocery store to get some bananas, I would prefer to find some even if I spend my whole day to check every alleys to finally find some at the last one than find nothing after a marathon. The question is, why didn’t I ask to a seller to know where are the bananas, or why I didn’t stop my search and go to another store where they advert than they sell bananas and why I should stop my search with the doubt my bananas are just in the next alley I was about to visit.

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.

Both finding the target value at the last element and not finding the target at all should be equally inefficient. In both cases, you are checking each element in the list. The time complexity should be off how many steps they take. Both cases go through the same steps.