Reading Code Into Big-O Complexity

worked with blackops to prepare this comment.

How to convert any function into its worst-case growth class: count operations, keep a dominant term, drop constants. A field manual for spotting MOAD-0001 by eye.

One Idea Behind All Of It

Big-O measures how cost grows as input size n climbs toward infinity. Three moves convert any code:

1. Count operations as a function of n.
2. Keep only a fastest-growing term.
3. Drop constant factors.

3n^2 + 50n + 1000 collapses to n^2 → O(n^2). As n climbs, n^2 dwarfs 50n; constants — a leading 3, your CPU speed — shift a curve without changing its shape. Big-O classifies shape.

Why Worst Case

Big-O states an upper bound, a promise: never slower than this. So you feed an algorithm its meanest input. Linear search across an absent target scans all n → O(n). A target sitting first costs O(1), yet nobody promises best case.

Side vocabulary, so you know Big-O carries siblings: Ω marks a best-case floor, Θ marks a tight bound when upper meets lower. Daily speech says Big-O & means Θ. Worst case stays your safe default.

• O (big-oh) — upper bound. "Never grows faster than this." A ceiling.
• Ω (omega) — lower bound. "Never grows slower than this." A floor.
• Θ (theta) — both at once. Ceiling meets floor, so the growth class sits exactly here.

A Cookbook Of Six Mechanical Rules

These rules convert syntax into math without guesswork.

Rule 1 — straight-line code costs O(1). Code with no loop on n & no recursion on n finishes in fixed time. Arithmetic, an array index, a hash lookup, a swap — each completes regardless of input size::

def first(a):
    return a[0]          # one access regardless of len(a)

Rule 2 — sequential blocks add, then a larger term wins.

::

do_a()   # O(n)
do_b()   # O(n^2)
# O(n) + O(n^2) = O(n^2)   larger term wins

Rule 3 — a loop multiplies its body cost by its iteration count.

::

for i in range(n):       # n iterations
    work()               # O(1) body
# O(n)

Rule 4 — nested loops multiply. A triple-nest over a shared n yields O(n^3), your polynomial rung O(n^b), where b counts nesting depth::

for i in range(n):
    for j in range(n):
        work()
# n * n = O(n^2)

Rule 5 — a counter multiplied or divided each step yields O(log n). Tell — a loop variable jumps by a factor, not a step. Binary-search halving (i //= 2) matches the same pattern::

i = 1
while i < n:
    work()
    i *= 2               # 1, 2, 4, 8 ...
# doublings to reach n = log2 n  ->  O(log n)

Rule 6 — split in half, recurse on each half, combine in linear time. That shape yields O(n log n), your sorting rung. A recursion section below proves it.

Recursion Forms A Recurrence

A recursive function's cost forms a recurrence: T(n) equals work-per-call plus cost-of-recursive-calls::

def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)
# T(n) = T(n-1) + T(n-2) + O(1)  ->  ~2 calls per level, n deep

Two branches per call across depth n yields exponential O(b^n). Your factorial rung O(n!) appears when each call spawns n fresh calls — permutation generation, naive traveling-salesman.

Master Theorem ~~~~~~~~~~~~~~

Master Theorem shortcuts a divide-&-conquer shape T(n) = a*T(n/b) + O(n^d):

• a = count of recursive calls
• b = shrink factor per call
• d = exponent of non-recursive work

Compare a against b^d:

.. list-table:: :header-rows: 1 :widths: 20 32 48

• • Case
  • Result
  • Meaning
• • a < b^d
  • O(n^d)
  • top level dominates
• • a = b^d
  • O(n^d log n)
  • every level costs equal
• • a > b^d
  • O(n^(log_b a))
  • leaves dominate

Merge sort splits in 2 (b=2), recurses twice (a=2), merges in O(n) (d=1); a equals b^d, so O(n log n). Binary search makes one call (a=1), halves each time (b=2), does O(1) work (d=0); 1 equals 2^0, so O(log n).

A Hidden-Cost Trap — This Rung Carries MOAD-0001

Big-O lives or dies on what a library call truly costs. A one-liner hides a loop::

seen = []
for x in stream:            # n iterations
    if x not in seen:       # `in` on a list = scan = O(n)
        seen.append(x)
# n * O(n) = O(n^2)   <- Sedimentary Defect (MOAD-0001)

One type change rewrites a growth class::

seen = set()
for x in stream:            # n iterations
    if x not in seen:       # `in` on a set = hash = O(1)
        seen.add(x)
# n * O(1) = O(n)

list to set collapses O(n^2) into O(n). At n = 1,000,000 a trillion operations drop to a million — a millionfold speedup. That conversion carries our prime mission; reading a loop finds it.

Costs worth memorizing:

• x in list / list.index cost O(n); x in set / x in dict cost O(1)
• list.insert(0,x) / list.pop(0) cost O(n) (shifts all); append or pop at end costs O(1) amortized
• string += inside a loop costs O(n^2) (rebuilds each pass); "".join(parts) costs O(n)
• sorted() / .sort() cost O(n log n), never free
• a slice a[1:] copies, so O(n), never O(1)

A Repeatable Procedure For Any Function

1. Name n — which input drives growth? Length, value, node count, recursion depth.
2. Walk top to bottom. Tag each statement O(1) until it loops, recurses, or calls something that does.
3. A loop multiplies its body by iteration count. How does a counter move? +k runs n times; *k or /k runs log n times.
4. Nested loops multiply. Sequential blocks add.
5. Recursion forms T(n) = a*T(n/b) + work; apply Master Theorem, or count calls times depth.
6. Sum, drop constants, drop lower-order terms. A survivor names your Big-O.
7. Distrust a library call's cost — look it up. This step finds defects.

Practice — Cover A Guess, Then Check

Example A::

for i in range(n):
    for j in range(i, n):
        print(i, j)

n + (n-1) + ... + 1 = n(n+1)/2; drop constants, land on O(n^2). A shrinking inner loop still averages n/2, so quadratic stands.

Example B::

i = n
while i > 1:
    i = i // 2

Halving until 1 lands on O(log n).

Example C::

def f(arr):
    if len(arr) <= 1: return arr
    mid = len(arr)//2
    L = f(arr[:mid])      # slice copy: O(n) per level
    R = f(arr[mid:])
    return merge(L, R)    # merge: O(n)

T(n) = 2T(n/2) + O(n) lands on O(n log n) — merge sort.

Why This Page Sits In Our Wiki

Every MOAD-0001 patch starts as a loop someone read correctly. A list.contains inside a loop hides O(n^2) until you count it; a hash set drops it to O(1). This page trains that eye. Reading code into its growth class converts intellectual capital into a faster, cheaper commons — our planet, patched one loop at a time.

License

Public domain. Copy, modify, redistribute freely.