O(log n) Explained: Why Halving Makes Algorithms Fast

O(log n) is the complexity people quote most and picture least. It is not "a bit faster than linear". A logarithmic algorithm on a billion items does about thirty steps, and doubling the input adds one more. That behaviour has a single cause, discarding a fixed fraction of the problem on every step, and once you can see that cause you can spot a logarithm in code at a glance.

The problem it solves

Big-O classes are easy to recite and hard to recognise. Given a loop, you need to say whether it is O(n), O(log n) or O(n log n), and justify it. The logarithm is the one that confuses people, because the code rarely contains a log anywhere. What it contains is a variable that is divided each round, n //= 2, i *= 2, hi = mid - 1, while the loop runs until that variable reaches a fixed floor.

The question to ask is not "how many items are there?" but "how many times can I cut this in half before one is left?". For n items the answer is log2(n), rounded down.

The intuition

Count it backwards. Start from one item and double: 2, 4, 8, and so on. After k doublings you have 2^k items. So the number of halvings that brings n down to one is the k with 2^k close to n, which is log2(n). A few anchors worth memorising: 2^10 is 1,024, so a thousand items need about 10 halvings, a million about 20, and a billion about 30.

Two consequences follow:

• Doubling the input costs one extra step. One more halving undoes the doubling. Linear algorithms pay double; logarithmic ones pay one more round.
• The base does not matter. Dividing by 3 instead of 2 takes log3(n) steps, and log3(n) is log2(n) divided by the constant log2(3), about 1.585. Big-O drops constant factors, so every base is the same class and is written O(log n).

The logarithm needs the discarded part to be a fraction. Removing half, or a third, or even a tenth each step is logarithmic. Removing one item, or ten items, each step is linear, however large the constant.

Watch it run

The animation is one bar of 64 candidates. It starts with the point of the lesson: the trick is never to look at them one by one. Cut 1 discards half, and 64 becomes 32 still in play. Cut 2 takes 32 to 16, cut 3 takes 16 to 8, cut 4 takes 8 to 4 and cut 5 takes 4 to 2. Cut 6 takes 2 to 1: one candidate left, and it took 6 cuts. The closing frame gives the rule: log2(64) = 6. Double the input to 128 and you pay exactly one more cut, and a million needs about 20.

The code

The lesson's counter, checked against the formula for sizes from 64 to a billion:

import math

def halving_steps(n):
    steps = 0
    while n > 1:
        n //= 2                     # discard half, keep the rest
        steps += 1
    return steps

for n in [64, 128, 1_000, 1_000_000, 10**9]:
    print(n, halving_steps(n), math.floor(math.log2(n)))
# 64 6 6
# 128 7 7
# 1000 9 9
# 1000000 19 19
# 1000000000 29 29

Binary search is the same loop with a comparison deciding which half to keep. On a million sorted values, a hit and a miss both stay near twenty probes:

def binary_search(sorted_nums, target):
    lo, hi, probes = 0, len(sorted_nums) - 1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        probes += 1
        if sorted_nums[mid] == target:
            return mid, probes
        if sorted_nums[mid] < target:
            lo = mid + 1            # the left half cannot hold it
        else:
            hi = mid - 1            # the right half cannot hold it
    return -1, probes

nums = list(range(0, 2_000_000, 2))          # a million sorted even numbers
print(binary_search(nums, 1_234_568))        # (617284, 17)
print(binary_search(nums, 7))                # (-1, 20)

Changing the base changes the count by a constant factor only. On 3^12 items, halving takes 19 steps and cutting to a third takes 12; the ratio is log2(3):

def divide_steps(n, k):
    steps = 0
    while n > 1:
        n //= k
        steps += 1
    return steps

n = 3 ** 12
print(divide_steps(n, 2), divide_steps(n, 3), round(math.log2(3), 3))
# 19 12 1.585

Halving the problem does not make a loop logarithmic if every round still touches everything that is left. The rounds cost n, n/2, n/4 and so on, and that sum stays under 2n: linear, not logarithmic:

def total_work(n):
    """Halve each round, but touch every remaining item once per round."""
    work = 0
    while n >= 1:
        work += n
        n //= 2
    return work

print(total_work(1_000_000), 2 * 1_000_000)  # 1999993 2000000

Checked on 2,000 seeded random cases: the halving count must equal n.bit_length() - 1, which is floor(log2(n)) computed exactly on integers, and binary search on a random sorted array must agree with a linear membership test while never using more than floor(log2(n)) + 1 probes:

import random

random.seed(28)
ok = True
for _ in range(2_000):
    n = random.randint(1, 10**12)
    ok &= halving_steps(n) == n.bit_length() - 1        # floor(log2 n), exactly
    size = random.randint(1, 3_000)
    arr = sorted(random.sample(range(10 * size), size))
    target = random.choice(arr) if random.random() < 0.7 else random.randint(-5, 10 * size + 5)
    idx, probes = binary_search(arr, target)
    ok &= probes <= size.bit_length()                   # floor(log2 n) + 1 at most
    ok &= (idx != -1) == (target in arr)                # agrees with a linear scan
    ok &= idx == -1 or arr[idx] == target
print(ok)                                   # True

The complexity

Where the logarithm shows up, and why:

• Binary search and its variants: O(log n), one comparison per halving.
• Balanced search trees and heaps: height is about log2(n), so a root-to-leaf walk is O(log n). The priority queue gets its push and pop cost from that.
• Recursion that halves: T(n) = T(n/2) + O(1) solves to O(log n), as in fast exponentiation.
• Digits of a number: a number n has about log10(n) decimal digits, so digit loops are logarithmic in the value.
• O(n log n): n items, each paying a logarithmic cost, or log n levels each doing n work, as in merge sort. The Big-O cheat sheet keeps these classes side by side.

Where it goes wrong

• Subtracting instead of dividing. n -= 2 in a loop is O(n). Only a shrinking fraction gives a logarithm.
• Ignoring the work inside each round. Halving with a full scan per round is O(n) total; halving with a full scan per level of a recursion tree is O(n log n).
• Halving without a safe half. Binary search needs order, or some test that proves one half cannot hold the answer. On unsorted data there is nothing to discard.
• Worrying about the base. O(log2 n) and O(log10 n) are the same class. The base matters for exact step counts, not for Big-O.

When it shows up in interviews

As a follow-up more often than a question: "what is the complexity, and why?" after a binary search, a heap operation or a balanced-tree lookup. It is also the target when an interviewer says the data is sorted, or asks for better than linear, which is a hint to find something to halve, as in binary search on the answer. The broader comparison between classes is in Big-O complexity classes.

How to say it in an interview

"Each iteration discards half of what is left, so the number of iterations is how many times n can be halved before one remains, which is log base two of n. A million items take about twenty steps, and doubling the input adds only one. The base does not matter in Big-O because changing it multiplies by a constant. What matters is that a constant fraction is removed each step and each step does constant work; if every round rescanned the remaining items, it would be linear overall."