Advanced Algorithms and Recursion: Question 7

Worked solution

Comparing the two algorithms’ worst-case complexity

In the worst case, linear search may have to check every single element before finding the target (or confirming it is absent), one comparison after another. Because the number of comparisons grows in direct proportion to the number of elements, linear search’s worst-case time complexity is O(n).

Binary search, applied to a sorted array, compares the target against the middle element and discards the half of the array that cannot contain it, repeating this on the remaining half each time. Each comparison roughly halves the number of elements still to be searched, so the number of comparisons needed grows much more slowly than n itself. Specifically in proportion to how many times n can be halved before reaching 1. This gives binary search a worst-case time complexity of O(log n).

As n increases, O(log n) grows far more slowly than O(n): for example, doubling n adds only one extra comparison in the worst case for binary search, but can add up to n extra comparisons for linear search. This is why option C is correct.

Why the other options are wrong

• A: reverses the two complexities. Linear search is the O(n) algorithm and binary search is the O(log n) algorithm, not the other way round.
• B: binary search does not need to examine every element in the worst case; halving the search space at each step is precisely what makes it faster than linear search for large n.
• D: linear search is not constant time. Its worst case still depends on n, since it may need to check every one of the n elements when the target is absent or is the last element checked.

Final answer

C. Linear search is O(n) and binary search is O(log n); binary search’s worst-case number of comparisons grows much more slowly than linear search’s as n increases.