Unit 8 Summary

Math for CS · Axiom Academy

Everything you need to know, condensed We use O , , and to describe how algorithms scale as input size grows. O(g(n)) — upper bound: f(n) grows no faster than g(n) — lower bound: f(n) grows at least as fast as g(n) — tight bound: f(n) grows at the same rate as g(n) Recurrences and the Master Theorem Recursive algorithms yield recurrences. The three main solving techniques: Substitution: Guess + induction proof Recursion tree: Sum work at each level Master theorem: For , compare c vs Quadratic sorts (bubble, insertion, selection): O(n^2) worst case. Simple but slow on large inputs. Merge sort: always. Stable. Uses O(n) extra space. Quicksort: average, O(n^2) worst. Fastest in practice with randomized pivots. Lower bound: Comparison-based sorting requires (decision tree argument). Non-comparison sorts (counting, radix, bucket) can achieve O(n) by exploiting key structure. Hash tables provide expected O(1) insert, delete, and lookup Chaining: Each slot stores a linked list. Performance depends on load factor . Open addressing: Probe for open slots (linear, quadratic, or double hashing). More cache-friendly. Keep and resize (double the table) when needed. Worst case is O(n) but essentially never happens with a good hash function. Las Vegas: Always correct, random running time (e.g., randomized quicksort) Monte Carlo: Bounded time, correct with high probability (e.g., Miller-Rabin primality test)

This is the written version of the interactive lesson above. See the full Math for CS course.