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

Concept: the worst-case time complexity of an algorithm is expressed as Θ(f(n)) — the TIGHT asymptotic bound (both upper and lower) on the number of elementary operations it can ever be forced to perform, over ALL possible inputs of a given size n, never the average or best case. (A plain O(f(n)) bound alone only guarantees an upper limit, not that the bound is tight.) Different algorithms belong to different growth-rate classes, ordered Θ(log n) < Θ(n) < Θ(n log n) < Θ(n²) …, and two algorithms “match” in worst case only when they sit in the SAME class.

Application: trace binary search's worst case on a sorted array of n elements, then place every offered option in its own growth-rate class.

1. Compare the target with the middle element of the current search range.

2. If it matches, the search stops immediately.

3. Otherwise, discard the half of the range that cannot contain the target and repeat on the remaining half — the range size is roughly halved at every step.

4. In the worst case (target absent, or confirmed only at the final comparison), this halving continues until one element remains — about log₂ n comparisons in total. Hence binary search's worst-case complexity is Θ(log n).

Placing each offered algorithm's own worst-case complexity next to binary search's makes the mismatch explicit:

Cross-check: Θ(log n) is strictly smaller than both Θ(n) and Θ(n log n), so binary search's worst case cannot coincide with linear search's, interpolation search's, or merge sort's worst case. No offered algorithm matches — the correct choice is “none of the above.”