O(log n): The Power of Halving

The power of halving

There is one more growth family you will meet constantly: O(log n), logarithmic time. It shows up whenever each step throws away half of what is left.

Think of the number-guessing game. I pick a number from 1 to 1000, you guess 500, I say "higher", and instantly 500 possibilities are gone. Each guess halves the range.

log₂ n just answers: how many times can you halve n before you reach 1? No other math needed. Let's count halvings directly.

Counting halvings directly

Since log₂ n is nothing more than the number of halvings, a loop can count it.

def halvings(n):
    steps = 0
    while n > 1:
        n = n // 2
        steps += 1
    return steps

for n in [8, 1024, 1000000]:
    print(n, halvings(n))

Output

8 3
1024 10
1000000 19

Eight halves to four, then two, then one, which is the 3. A million collapses to 1 in only 19 steps, and that count is log₂ n rounded down.

Compare that with the linear count from lesson 1-2, where a million items meant a million steps. The same input size costs 19 operations here instead of 1,000,000, which is the reason this growth family is worth recognizing on sight.

Binary search: halving in action

If a list is sorted, it can be searched the guessing-game way. Look at the middle item. Too small, and the target must be in the right half. Too big, and it must be in the left half. Either way, half the list is eliminated by one comparison.

That is binary search, O(log n) in place of the O(n) scan from lesson 1-1, and the gap becomes absurd at scale.

Two requirements come attached. The data must already be sorted, and you need instant access to the middle item.

Both are real constraints rather than technicalities. Sorting costs something up front, which only pays off across many searches, and the instant middle access is exactly what a linked list cannot provide. Keep that second requirement in mind, because it decides arrays against linked lists in unit 4.

Implementing binary search

Two indexes, lo and hi, bound the region that could still contain the target. Each comparison shrinks that region by half.

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

nums = list(range(0, 2000, 2))
print(binary_search(nums, 1998))
print(binary_search(nums, 0))
print(binary_search(nums, 777))

Output

(999, 10)
(0, 9)
(-1, 10)

The list holds 1000 sorted even numbers. When items[mid] < target the target can only lie to the right, so lo = mid + 1, and when items[mid] > target it can only lie to the left, so hi = mid - 1. Both moves skip past mid itself, which has already been ruled out.

The loop ends when lo > hi, meaning the region has closed to nothing and the target is absent. That is the 777 case: the value is odd and the list holds only even numbers, so the search exhausts the range in 10 checks and returns -1.

Notice that a missing value costs the same as a present one at the far end, around 10 checks out of 1000 items. Binary search does not get slower when it fails.

For 2,000,000 sorted items, binary search needs about 21 checks.

Doubling n adds exactly one halving. The first check cuts 2,000,000 down to 1,000,000, and from there the remaining work is the same 20 checks as before.

Stated as arithmetic, log₂(2n) = log₂ n + 1. That single-step penalty for doubling the input is why O(log n) barely notices growth, and why a search structure built on halving keeps working as a dataset goes from thousands to billions.

Where halving shows up this week

O(log n) is not an interview curiosity. It is load-bearing infrastructure you touch as a working engineer.

• git bisect finds the commit that broke your build by binary-searching the commit history, so 1,000 suspect commits take about 10 test runs instead of 1,000.
• Database indexes answer a query like WHERE id = 7423 by walking a balanced search tree rather than scanning the table. That is the halving idea grown into a structure, and unit 7 builds it.
• Python's bisect module binary-searches any sorted list for you, which is why you rarely hand-write the loop outside of interviews.

The common thread is a bargain. Someone paid once to keep the data sorted, or tree-shaped, so that every later question costs log n instead of n.

That framing is worth carrying forward, because it explains why so many structures in this course spend effort on insertion. The cost goes in where the data arrives, so that it does not have to be paid every time the data is read.

Ordered from fastest-growing to slowest, the families run O(n²), then O(n), then O(log n), then O(1). So the worst of them is O(n²).

Quadratic work explodes as n grows, linear work grows in proportion, logarithmic work barely grows at all, reaching about 20 for a million items, and constant work does not grow.

Lesson 1-2 put the numbers on the extremes. At n = 1,000,000 the quadratic family needs 10¹² steps where the constant family needs a handful, which is the difference between hours and instantly. Recognizing which family a piece of code belongs to is therefore the first question to ask about it, well before any attempt at micro-optimization.