Algorithm complexity

The right data structure changes everything

Finding one letter in an unsorted pile means going through the pile. Finding it in a wall of labeled pigeonholes means walking straight to the right one. Checking x in some_list is the pile: it walks the list item by item, which is O(n). Checking x in some_set is the wall: it jumps straight to the answer, O(1) on average. A set and a dict use a hash table, which the next lesson builds from scratch. For now, feel the difference:

import time

n = 20000
as_list = list(range(n))
as_set = set(as_list)
lookups = range(n - 500, n)          # 500 values near the end of the list

start = time.perf_counter()
hits = sum(1 for x in lookups if x in as_list)
list_time = time.perf_counter() - start

start = time.perf_counter()
hits = sum(1 for x in lookups if x in as_set)
set_time = time.perf_counter() - start

print("list:", round(list_time * 1000, 1), "ms")
print("set: ", round(set_time * 1000, 2), "ms")
print("set is about", round(list_time / set_time), "times faster here")

The exact numbers depend on your machine. The gap is the point, and it widens as n grows.

Halving: where log n comes from

Guess a number between 1 and 1,000,000, and after each guess you're told "higher" or "lower". Always guess the middle and you halve what's left each time. It takes at most 20 guesses, because halving a million 20 times gets you to one. That count is the logarithm base 2 of n, and it grows very slowly: a billion items need only 30 halvings.

n = 1_000_000
halvings = 0
while n > 1:
    n = n // 2
    halvings += 1
print(halvings, "halvings to go from a million to one")

n, steps = 1_000_000, 0
while n > 1:
    n //= 2
    steps += 1
print(steps)

def has_dupes_slow(emails):
    checks = 0
    for i in range(len(emails)):
        for j in range(i + 1, len(emails)):
            checks += 1
            if emails[i] == emails[j]:
                return True, checks
    return False, checks

def has_dupes_fast(emails):
    seen = set()
    checks = 0
    for e in emails:
        checks += 1
        if e in seen:
            return True, checks
        seen.add(e)
    return False, checks

emails = [f"user{i}@shop.test" for i in range(2000)]
print("slow:", has_dupes_slow(emails))
print("fast:", has_dupes_fast(emails))

Big O in AI systems

The same thinking explains limits you met earlier in the course:

• Attention compares every token with every other token, the handshakes at the party again, so its cost is O(n²) in the length of the context. Doubling the context roughly quadruples that part of the work. That's why long context costs more, and why researchers work on cheaper attention.
• Similarity search that compares a question with every stored embedding is O(n). That's fine for ten thousand documents and too slow for a billion, which is why vector databases build an index that skips most of them.
• Generating text takes one model step per output token, so it's O(n) in the reply's length. Long answers take longer.

What Big O doesn't tell you

It isn't seconds. Big O describes how the work grows as the input grows, on any machine. A faster laptop changes the seconds and leaves the Big O alone. That's why it's useful: it predicts what happens at ten times the data, before you get there.

Constants get dropped. 3n + 7 and n are both O(n), because at a large size the shape of the curve matters more than the multiplier. So O(n) code can lose to O(n²) code on small inputs, and you shouldn't care. It's the large inputs that hurt.

A quick test on a small sample proves little. A dinner for four tells you nothing about catering a wedding. Quadratic code looks fine on 100 rows. On a million rows it takes about 100 million times as long. This is the classic way software works on a laptop and falls over in production, so try your code on realistic sizes before you trust it.

in isn't one thing. x in my_list checks items one at a time, which is O(n). x in my_set goes almost straight there, which is O(1). Inside a loop, that one word decides whether your program takes seconds or hours.