Big O Notation
Big O describes the upper bound on an algorithm's growth rate as input size N approaches infinity, ignoring constants and lower-order terms.
Big O is like rating restaurants by stars (1-5) not exact scores. A 4.1 and a 4.9 are both '4-star' — you drop the decimals (constants) and only care about the star tier (dominant term).
Common classes in order: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). Drop constants and lower-order terms: 3n² + 5n + 100 = O(n²). For multiple variables (e.g., a graph with V vertices and E edges), keep both: O(V + E). Worst-case is the default unless stated; best-case uses Omega (Ω); tight bound uses Theta (Θ).
Big O is a mathematical upper bound — O(n) includes O(1) algorithms by definition. In practice 'Big O' is used to mean tight bound (Θ). Constants matter at small N: O(n²) with c=0.0001 beats O(n) with c=10000 for small inputs. Master theorem resolves divide-and-conquer recurrences: T(n) = aT(n/b) + f(n) — memorize the three cases. For probabilistic algorithms, average-case analysis uses expected value. NP-hard problems have no known polynomial solution — knowing when a problem is NP-complete saves you from hunting for an efficient algorithm.
I state Big O for both time and space upfront. I drop constants and lower-order terms, keep the dominant term, and clarify worst vs average when it matters — for example, quicksort is O(n²) worst case but O(n log n) expected. For hash map operations I say 'amortized O(1)' not just 'O(1)' to be precise. I also think about N's practical size — sometimes an O(n log n) algorithm with better cache behavior beats an O(n) algorithm with many cache misses in practice.
O(2n) and O(n) are the same — you CANNOT compare algorithms by their Big O class alone when constants differ significantly. Also: nested loops are not always O(n²); if the inner loop runs a fixed number of times, the whole thing is still O(n).