O(log n): Logarithmic Time

A linear scan answers "is 251 in this list?" by reading items until it meets 251 or runs out, so a list twice as long can cost twice the reads. A sorted list allows a different move. Read the middle item. If it is smaller than 251, everything to its left is smaller too, and the whole left half is discarded in 1 step; if it is larger, the right half goes instead. Each read cuts the remaining range in half, and the search stops when the range holds the target or holds nothing.

The number of reads is the number of times n can be halved before 1 item is left. That count is the base-2 logarithm of n, written log n, and an algorithm whose work grows this way is O(log n). The practical reading: doubling the input adds 1 read.

Sorted items (n)Linear scan, worst caseHalving search, worst case
1616 reads5 reads
1,0001,000 reads10 reads
1,000,0001,000,000 reads20 reads
1,000,000,0001,000,000,000 reads30 reads

Watching the range shrink

The program below is binary search. It keeps 2 boundaries, lo and hi, around the slice of the list that could still hold the target. Each pass of the while loop reads the item at mid, halfway between them, and moves 1 boundary past it. Follow the gap between the boundaries: 16 candidates, then 8, then 4, then 1.

user_ids = [103, 118, 127, 140, 152, 166, 171, 189,
            204, 215, 233, 247, 251, 268, 279, 295]
target = 251
lo = 0
hi = len(user_ids) - 1
checks = 0
found_at = None
while lo <= hi:
    mid = (lo + hi) // 2
    checks += 1
    print(f"check {checks}: index {mid} holds {user_ids[mid]}")
    if user_ids[mid] == target:
        found_at = mid
        break
    if user_ids[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(f"found at {found_at} after {checks} checks")
check 1: index 7 holds 189
check 2: index 11 holds 247
check 3: index 13 holds 268
check 4: index 12 holds 251
found at 12 after 4 checks

The search found 251 on the 4th read and never looked at 103, 118 or 10 other ids. A target larger than every id in this list costs 5 reads, the worst case for 16 items, matching the table above.

Why an index makes a lookup fast

A table stores rows in the order they arrived. A query for user 251's plays cannot know where those rows sit, so it reads every row and checks user_id on each: O(n). An index on user_id is a second structure holding that column's values in sorted order, each paired with the position of the row it came from. The engine halves its way through the sorted values to the first 251, then follows the stored positions back to the rows.

SELECT
  track_id
FROM plays
WHERE user_id = 251

Real indexes branch wider than 2. Keys are packed into pages holding hundreds of entries each, arranged as a tree: the top page splits the key range into hundreds of slices, each pointing to a page that splits its slice again. Every step still discards most of what remains, so the cost stays O(log n) with a far larger base.

An events table is indexed on user_id. It grows from 10 million rows to 40 million. How does the work of an indexed lookup for a single user_id change?

Why the boundary moves past mid

Once user_ids[mid] has been read and is not the target, index mid is ruled out, so the next range has to leave it behind. The update lo = mid keeps it in, and that breaks the loop. Search the 16 ids for 300, larger than all of them: the boundaries close in until lo is 14 and hi is 15. Then mid is 14, 279 is smaller than 300, and lo = mid sets lo to 14 again. Every later pass computes the same mid, reads the same id and makes the same move, so the loop never ends. The update lo = mid + 1 shrinks the range by at least 1 item per pass, and the trace below shows it stopping after 5 reads.

PasslohimidId readNext move
10157189lo = 8
281511247lo = 12
3121513268lo = 14
4141514279lo = 15
5151515295lo = 16
61615not computednonelo > hi, loop ends, found_at stays None

About this lesson

This section is part of the Complexity: Intermediate lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.