18. Complexity & Asymptotic Analysis

Level: Intermediate You'll use this for: choosing the right algorithm/data structure at scale, and estimating brute-force attack feasibility.

Big-O notation

Big-O describes how an algorithm's resource usage (time or memory) grows as input size n grows — the worst-case upper bound, ignoring constant factors, because constants stop mattering as n gets large.

Complexity	Name	Example
`O(1)`	constant	hash table lookup
`O(log n)`	logarithmic	binary search (Ch. 5)
`O(n)`	linear	scanning a list once
`O(n log n)`	linearithmic	efficient sorting (merge sort, quicksort avg)
`O(n²)`	quadratic	nested loops, naive sorting
`O(2^n)`	exponential	brute-force subset enumeration
`O(n!)`	factorial	brute-force traveling salesman

import time

def linear_search(lst, target):        # O(n)
    return target in lst

def binary_search(sorted_lst, target): # O(log n) — requires sorted input
    lo, hi = 0, len(sorted_lst) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_lst[mid] == target: return mid
        elif sorted_lst[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

How to derive Big-O by hand: count the operations

Linear search on a list of n items: in the worst case (target is last, or missing entirely), the loop runs once per element — n comparisons. Drop the word "comparisons," keep the shape: O(n).

Binary search on a sorted list of n items: each pass through the while loop discards half the remaining candidates. Starting from n items, after 1 comparison you have n/2 left, after 2 you have n/4, after k comparisons you have n/2^k left. The loop stops once 1 item remains:

n / 2^k = 1   =>   2^k = n   =>   k = log2(n)     (Ch. 5's log rule, applied)

So for n = 1,000,000, binary search needs at most log2(1,000,000) ≈ 20 comparisons — count them by hand for a small case to see the pattern: n=16 -> 8 -> 4 -> 2 -> 1 is 4 halvings, and log2(16) = 4, confirming the formula.

The general method for any piece of code: count how many times the innermost operation runs as a function of n. A single loop over n items is O(n). A loop inside another loop, both over n, multiplies: O(n) × O(n) = O(n²). A loop that halves its remaining work each pass (like binary search) is O(log n). Reading nested loops and halving patterns this way is literally how you derive a Big-O class without memorizing a table of answers.

Why the growth rate matters more than the constant

At n = 10, an O(n²) algorithm might beat an O(n log n) one due to constant factors/overhead. At n = 10,000,000, O(n²) is catastrophically worse — n² is 10 trillion operations vs. n log n's ~230 million. This is why "premature optimization" advice applies to constants, not to asymptotic class — algorithm choice matters far more at scale than micro-optimization.

Worked example: brute-force time estimate

If a keyspace has 2^128 possible keys (Ch. 15) and an attacker can try 10^12 keys/second (a fast, dedicated cracking rig), how long to brute force?

keyspace = 2**128
attempts_per_sec = 10**12
seconds = keyspace / attempts_per_sec
years = seconds / (60*60*24*365)
print(f"{years:.2e} years")   # ~1.08e19 years — vastly longer than the age of the universe

This single Big-O-adjacent calculation (exponential keyspace growth vs. linear attacker speed growth) is why doubling a key length doesn't double the difficulty — it squares it, which is the entire mathematical argument for why AES-256 and RSA-2048+ are considered safe against brute force for the foreseeable future (Ch. 24, 26).

Real-life engineering ties

SWE: choosing O(1) hash-map lookups over O(n) list scans at scale; recognizing an accidental O(n²) (e.g., a list.remove() or string concatenation inside a loop) before it becomes a production incident.
AI: attention mechanism complexity is O(n²) in sequence length — the entire reason "long context" is expensive and the motivation behind efficient-attention research (sparse/linear attention).
Network: routing table lookup complexity, packet processing pipelines designed for O(1)/O(log n) per-packet cost at line rate.
Security: brute-force feasibility calculations (above), and recognizing algorithmic-complexity attacks (an attacker crafting input that forces your O(n²) worst-case path — e.g., hash-flooding attacks that force hash-table collisions deliberately, CWE-407).

More real-life examples:

Cloudflare's July 2019 global outage was caused by a single regular expression with catastrophic backtracking — effectively an accidental O(2^n) worst case — that pegged CPU to 100% across their edge network; this failure mode has a name, ReDoS (Regular Expression Denial of Service), and is a listed CWE (CWE-1333).
Python's and Java's default sort (Timsort) was engineered to be O(n log n) worst-case while detecting and exploiting already-sorted runs in real data to approach O(n) best-case — a deliberate complexity-class engineering decision, not an accident.
Database query planners (PostgreSQL's EXPLAIN ANALYZE, MySQL's optimizer) choose between an index scan (O(log n)) and a full table scan (O(n)) based on estimated row counts — reading a query plan is a direct, daily application of Big-O reasoning.
Hash-flooding DoS attacks (CWE-407) exploit predictable hash functions to force many keys into the same bucket, degrading a hash table's expected O(1) lookup into O(n) — the reason modern language runtimes (Python, Ruby, PHP) randomize their hash seed at process start.

Common mistake

Reporting Big-O without stating which case (best/average/worst). Quicksort is O(n log n) average but O(n²) worst-case on adversarially chosen (or already-sorted) input — a distinction that matters a lot if an attacker controls your input.