The worst-case time complexity of binary search matches with:

2023

The worst-case time complexity of binary search matches with:

  1. A.

    interpolation search

  2. B.

    linear search

  3. C.

    merge sort

  4. 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'.

Explore the full course: Coding For Placement