Exam-style question
Try this first
Explain why the time complexity of a linear search is O(n). Include what can happen when the target is near the end of the list or is not present.
Model answer
What a good answer should say
- A linear search checks list items one at a time.
- If there are n items, the search may need to compare the target with every item.
- This can happen when the target is near the end of the list or when the target is not present.
- The number of comparisons can therefore grow in proportion to n, so the time complexity is O(n).
Explanation
Why this works
The key point is that the search may inspect all n elements. Finding a target early can stop the search sooner, but it does not change the overall O(n) classification because the amount of work can still grow linearly with the list size.
Common mistake
No common mistake is linked to this question yet.