PART 4 · DSA AND COMPLEXITY · CHAPTER 14

Big-O in plain words: how work grows

FreeLesson 39 of 78

Big-O answers one question: when the input gets 10 times bigger, how much more work does my code do? Not seconds, but how the work grows.

Think of finding one customer's name in a register. If the register is unsorted, you may read every line: double the register, double the work. That is O(n). If it is sorted, you open the middle and throw away half each time: a register 1,000 times bigger needs only about 10 more looks. That is O(log n). If you compare every name with every other name to find duplicates, double the register and the work goes up 4 times. That is O(n²).

STEPS NEEDED AS N GROWSPYTHON 3.12

import math

rows = [("O(1)", lambda n: 1),
        ("O(log n)", lambda n: math.log2(n)),
        ("O(n)", lambda n: n),
        ("O(n log n)", lambda n: n * math.log2(n)),
        ("O(n^2)", lambda n: n * n),
        ("O(2^n)", lambda n: 2 ** n)]
sizes = [10, 1_000, 100_000]
print(f"{'growth':<11}" + "".join(f"{s:>16,}" for s in sizes))
for name, f in rows:
    cells = ""
    for s in sizes:
        if name == "O(2^n)" and s > 64:
            cells += f"{'too many':>16}"
        else:
            cells += f"{f(s):>16,.0f}"
    print(f"{name:<11}" + cells)

Output

growth                   10           1,000         100,000
O(1)                      1               1               1
O(log n)                  3              10              17
O(n)                     10           1,000         100,000
O(n log n)               33           9,966       1,660,964
O(n^2)                  100       1,000,000  10,000,000,000
O(2^n)                1,024        too many        too many

O(n log n) for a lakh of rows is about 17 lakh steps. O(n²) is 10 billion. That gap is why one solution finishes in a blink and the other times out.

MEASURED: DOUBLE N, SEE WHAT HAPPENSPYTHON 3.12

import random, time

def has_dup_nested(xs):            # O(n^2): compare every pair
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            if xs[i] == xs[j]:
                return True
    return False

def has_dup_set(xs):               # O(n): one pass with a set
    seen = set()
    for x in xs:
        if x in seen:
            return True
        seen.add(x)
    return False

def ms(fn, xs):
    t = time.perf_counter(); fn(xs)
    return (time.perf_counter() - t) * 1000

for n in (1_000, 2_000, 4_000):
    xs = random.sample(range(10 * n), n)   # no duplicates: worst case
    a, b = ms(has_dup_nested, xs), ms(has_dup_set, xs)
    print(f"n={n:>5}  nested {a:7.1f} ms   set {b:5.2f} ms")

Output

n= 1000  nested    21.1 ms   set  0.09 ms
n= 2000  nested    91.5 ms   set  0.35 ms
n= 4000  nested   348.7 ms   set  0.44 ms

The times are what this run measured when the book was built. Yours will differ.

Five rules for working it out

I Loops one after another add: O(n) + O(n) = O(n). I Loops inside loops multiply: a loop over n inside a loop over n is O(n²). I Drop constants: 3n + 5 is still O(n). Big-O is about growth, not exact counts. I Keep the biggest term: n² + n is O(n²). I Different inputs, different letters: orders x customers is O(n x m), not O(n²).

How big can n be?

If n is about	You can afford	Typical approach
20	O(2^n), O(n!)	Try every subset or order
1,000 to 5,000	O(n²)	Compare pairs
1 lakh to 10 lakh	O(n log n), O(n)	Sort, hash, one pass
Crores	O(n), O(log n)	Stream, binary search, or Spark

Rule of thumb: plain Python manages very roughly 10 million simple steps a second. Read the input size in the question and pick a complexity that fits.

Practice before you move on

Write a duplicate check for a list of ids with a nested loop and with a set, and time both on 2,000 ids.
Predict how the nested loop's time changes when the list doubles, then run it and check.