O(n) vs O(log n): Why It Matters

An O(log n) algorithm wins whenever it can repeatedly discard half of the remaining candidates instead of testing them one by one. That requires a strong extra condition: the data must be sorted, or at least ordered in a way that a comparison can rule out a whole half of the possibilities. Without that structure, no amount of cleverness lets you skip candidates, and the linear scan is genuinely the best you can do.

def linear_search(items, target):
    for i, value in enumerate(items):
        if value == target:
            return i
    return -1

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

data = list(range(0, 1000, 2))
print(linear_search(data, 500), binary_search(data, 500))

Both print 250, so they agree on the answer. They disagree on effort: the linear version may inspect up to 500 elements, while the binary version never needs more than ten probes because each step halves the search interval. Multiplying the input by a thousand multiplies the linear cost by a thousand and the binary cost by about ten.

The trade-off to state is that the logarithmic win is bought with a precondition. Sorting is itself O(n log n) or better, so for a single lookup on unsorted data, a linear scan wins overall. The moment you need many lookups on the same data, paying the sort once and then doing logarithmic lookups is the cheaper deal. That is the real trade-off an interviewer is listening for: the algorithm is only as good as the structure you maintain to feed it.

About twenty comparisons in the worst case. Each comparison splits the remaining search space in half, so after k comparisons the interval you still have to consider has shrunk by a factor of two to the power k. Solving two to the power k greater than or equal to one million gives k of roughly 19.9, and since you cannot make a fractional number of comparisons, you round up to twenty.

That is the whole trick, and it is worth understanding why it works rather than memorising the formula. A comparison against the middle element tells you one of three things: the target is there, the target is smaller and therefore cannot be anywhere to the right, or the target is larger and cannot be anywhere to the left. Each answer throws away roughly half of the remaining candidates. The logarithm is simply the number of times you have to halve a quantity to reduce it to about one.

Two caveats are worth volunteering. First, the halving only works because the data is sorted; on unsorted input the comparison tells you nothing about where to look next. Second, the count is about comparisons, not total time: each iteration also does index arithmetic and a loop check, so a binary search is not literally twenty times faster than a linear scan. The point stands regardless, because twenty against a million is a difference in the shape of the curve, not a difference in constants.

One more thing that trips people up: binary search on a list has O(1) element access in the C language and in Python's list type, but if the container were a linked list, reaching the middle would cost O(n) and the whole argument collapses.