Exam-style question
Try this first
Explain why binary search has a time complexity of O(log n). In your answer, describe what happens to the remaining search range after each comparison.
Model answer
What a good answer should say
- At each comparison, binary search checks the middle item of the current range.
- Depending on whether the target is greater or less than this item, approximately half of the remaining items are discarded.
- The process continues on the remaining half until the target is found or no items remain.
- Because the range is repeatedly halved, the number of comparisons increases logarithmically as n increases, giving a time complexity of O(log n).
Explanation
Why this works
The key feature is repeated halving. The algorithm does not examine every item in turn; each comparison substantially reduces the number of possible positions that still need to be checked.
Common mistake
No common mistake is linked to this question yet.