Algorithm Analysis Summary

Discrete Math · Axiom Academy

Let's review how complexity analysis predicts algorithm scalability and guides optimal algorithm selection for real-world problems. Definition: Big-O describes the upper bound of an algorithm's growth rate as input size n approaches infinity Asymptotic Behavior: Constants and lower-order terms don't matter for large n—focus on the dominant term Formal Definition: f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀ Related Notations: Big-Θ for tight bounds, Big-Ω for lower bounds—together they fully characterize complexity O(1) - Constant: Array access, hash table lookup (average case)—independent of input size O(log n) - Logarithmic: Binary search, balanced tree operations—halves the problem each step O(n) - Linear: Single loop through data, finding max/min—touches each element once O(n log n) - Linearithmic: Efficient sorting (merge sort, quicksort average), divide-and-conquer algorithms O(n²) - Quadratic: Nested loops, bubble sort—becomes impractical for large datasets O(2ⁿ) - Exponential: Brute-force subset enumeration—only feasible for tiny inputs Algorithm Complexity Reference Analyzing QuickSort Complexity Best Case - O(n log n): Each partition divides the array perfectly in half, creating a balanced recursion tree of depth log n with O(n) work per level Average Case - O(n log n): Random pivot selection gives expected balanced partitions. Most splits are "good enough" to maintain logarithmic depth

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