Exam-style question
Try this first
What does the time complexity O(n) mean for a linear search?.
- A.The number of comparisons is unrelated to the number of items.
- B.The number of comparisons can grow in proportion to the number of items.
- C.The search always makes exactly one comparison.
- D.The search always makes the same number of comparisons as a binary search.
Model answer
What a good answer should say
- The number of comparisons can grow in proportion to the number of items.
Explanation
Why this works
For a list with n items, a linear search may need to examine each item. Therefore, the amount of work grows linearly as n increases, giving a time complexity of O(n).
Common mistake
No common mistake is linked to this question yet.