The worst-case time complexity of binary search matches with:
2023
The worst-case time complexity of binary search matches with:
- A.
interpolation search
- B.
linear search
- C.
merge sort
- D.
none of the above
Attempted by 3 students.
Show answer & explanation
Correct answer: D
Concept: Time complexity describes how an algorithm's running time grows with input size n, written in Big-O notation. Two algorithms are said to have the same worst-case complexity only when they belong to the same asymptotic growth class (e.g., O(log n), O(n), or O(n log n)) - not merely because both happen to be search or sort procedures.
Application: Compare the worst-case time complexity of binary search with each option:
Algorithm | Worst-case time complexity |
|---|---|
Binary search | O(log n) |
Interpolation search | O(n) |
Linear search | O(n) |
Merge sort | O(n log n) |
Interpolation search and linear search both fall in the O(n) class, and merge sort is O(n log n); none of these equals binary search's O(log n).
Cross-check: For n = 1,024 sorted elements, binary search needs at most log2(1024) = 10 comparisons in the worst case, whereas linear search (and interpolation search under a skewed/adversarial distribution) can need up to 1,024 comparisons, and merge sort performs on the order of 1,024 x 10 ~ 10,240 elementary operations - orders of magnitude apart from binary search's logarithmic count.
Result: Since no listed algorithm shares binary search's O(log n) worst-case bound, the correct choice is 'none of the above'.