Complexity and Big-O

COMPLEXITY & BIG-O DSA · 01 — how an algorithm's cost GROWS with input size: the one lens for the whole track machines get faster every year, so counting seconds is useless. instead count OPERATIONS as a function of input size n, drop the noise, and keep the term that dominates as n grows. that's Big-O. 1 · BIG-O: the shape of growth Big-O is an UPPER BOUND on growth. drop constants & lower-order terms — as n→∞ only the biggest matters: O(2n + 3) -> O(n) O(n^2 + 100n) -> O(n^2) the ladder, best → worst: O(1) constant array index, hash lookup O(log n) logarithmic binary search, balanced tree (halve each step) O(n) linear scan an array once O(n log n) linearithmic good sorting (merge / quick) O(n^2) quadratic nested loops, bubble sort O(2^n) exponential all subsets, naive recursion O(n!) factorial all permutations, brute-force TSP ops n → O(1)/log n O(n) n log n O(n^2) O(2^n) 2 · WHY IT MATTERS (n = 1,000,000) O(log n) ~ 20 ops -> instant O(n) 1,000,000 -> instant O(n log n) ~ 20,000,000 -> a blink O(n^2) 1,000,000,000,000 -> ~minutes to hours O(2^n) more atoms than -> never (heat death) the universe has THAT gap — instant vs never — is the entire reason to care. a better Big-O beats a faster CPU every time. BEST / AVERAGE / WORST case: · quicksort: O(n log n) average, but O(n^2) worst (a bad pivot). · hash lookup: O(1) average, O(n) worst (everything collides). design for the case that matters — usually AVERAGE, but WORST for real-time / adversarial input. O vs Ω vs Θ: O = upper bound (ceiling) · Ω = lower bound (floor) · Θ = tight (both match). people say 'O(n)' casually but usually mean Θ(n) — the actual growth, not just a ceiling. 3 · TIME vs SPACE, and AMORTIZED cost complexity isn't only TIME — also SPACE (memory as a function of n), incl. the recursion call stack. they TRADE: memoization/caching spends space to save time; in-place algorithms spend time to save space. AMORTIZED analysis: the cost AVERAGED over a sequence, even if one step is occasionally expensive. the classic — a DYNAMIC ARRAY append (Python list, Go slice): full! double appends are usually O(1); when full it DOUBLES capacity and copies everything = O(n) that once. but doublings are rare (geometric: 1,2,4,8,16...), so averaged over all appends it's AMORTIZED O(1). this exact reasoning explains DDIA's LSM compaction cost and why 'append + occasionally reorganize' wins — the rare expensive step is paid for by the many cheap ones. 4 · HOW TO READ COMPLEXITY OFF CODE · a simple loop over n → O(n). · NESTED loops → MULTIPLY: two over n → O(n^2). · halving each step (i *= 2, or recursing on n/2) → O(log n). · RECURSION → draw the call tree: (nodes) × (work per node). fib(n) branches 2x each level, depth n -> O(2^n). · the DOMINANT term wins: O(n^2 + n) is just O(n^2). THE BIG CAVEAT (ties How-Computers-Work l.05): Big-O HIDES the constant — and the constant is often the CACHE. an O(n) linked-list walk can lose to O(n log n) array work, because pointer-chasing cache-misses (memory hierarchy). so: Big-O tells you how it SCALES (necessary), the constant/cache tells you how FAST it actually runs. pick the right complexity first, THEN measure. never optimize the constant on an O(n^2) that should be O(n log n). JARGON, DECODED Big-O = upper bound on growth (drop constants & lower terms) · O(1)/log/n/n log n/n^2/2^n/n! = the growth classes · linearithmic = n log n · n = input size Θ (theta) = tight bound (matches above & below) · Ω (omega) = lower bound · best/average/worst case = the input that gives least/typical/most cost · input-sensitive = cost depends on which input, not just its size time vs space complexity = ops vs memory as a function of n · amortized = cost averaged over a sequence of ops · memoization = cache results to trade space for time · in-place = uses O(1) extra space dominant term = the fastest-growing part (all that survives Big-O) · the cache caveat = Big-O ignores the constant, and the constant is often memory locality (l.05) · Master theorem = recurrence → complexity