Big O notation is a mathematical framework for describing the asymptotic behavior of algorithms as input size grows toward infinity. Born from computational complexity theory, it abstracts away hardware specifics and constant factors to reveal the fundamental scalability of codeβwhether an algorithm remains practical at scale or collapses under growing data. While Big O represents the upper bound (worst-case), companion notations like Big Omega and Big Theta capture lower bounds and tight bounds respectively. The key insight: an O(n) algorithm doubles runtime when input doubles, but an O(n^2) algorithm quadruples itβthis multiplicative difference dominates performance at scale, making complexity analysis the single most powerful lens for predicting real-world algorithmic behavior before a single line executes.
What This Cheat Sheet Covers
This topic spans 18 focused tables and 123 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Common Time Complexities
The most important complexity classes appear here ranked from fastest to slowest. Understanding where your algorithm falls on this scale β and the enormous gulf between adjacent classes at large input sizes β is the foundation of algorithmic reasoning.
| Complexity | Example | Description |
|---|---|---|
arr[5] | β’ Constant time β execution time independent of input size β’ direct access operations, hash table lookups (average), stack push/pop | |
while (n > 1): n = n // 2 | β’ Logarithmic time β halves the problem space each step β’ binary search, balanced tree operations, divide-and-conquer | |
for i in range(int(n**0.5)): check_divisor(i, n) | β’ Square root time β iterates up to square root β’ primality testing via trial division, some number theory algorithms | |
for i in range(n): print(arr[i]) | β’ Linear time β single pass through data β’ iterating arrays, linked list traversal, linear search in unsorted data | |
merge_sort(arr) | β’ Linearithmic time β optimal comparison-based sorting β’ merge sort, quicksort (average), heap sort | |
Sieve of Eratosthenes | β’ Slightly worse than linear β’ prime sieve algorithms that eliminate multiples logarithmically |