A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Big-O notation provides an upper bound on how an algorithm's runtime grows with input size, focusing on asymptotic behavior while ignoring constant factors and lower-order terms. It enables meaningful algorithm comparison independent of hardware. For example, linear search is O(n) while binary search is O(log n), making binary search vastly superior for large inputs despite higher constant factors.
Start with concrete examples by counting operations in simple loops and recursive functions, identifying the dominant term. Practice deriving Big-O for nested loops, divide-and-conquer recurrences, and data structure operations before moving to general complexity classes.
You already understand from algorithm design basics that algorithms can be compared by how efficiently they solve a problem, and from asymptotic notation that Big-O provides an upper bound on growth rate. This topic shifts focus from the mathematical definition to the practical skill of analyzing code to determine its Big-O complexity. The goal is to look at an algorithm — its loops, recursive calls, and data structure operations — and derive how its runtime scales with input size n.
The fundamental technique is counting the dominant operation. For a single loop that iterates n times and does constant work per iteration, the complexity is O(n). For two nested loops that each iterate n times, the inner loop executes n times for each of the n outer iterations, giving O(n²). If the inner loop depends on the outer variable — say, iterating from i to n — the total work is n + (n-1) + ... + 1 = n(n+1)/2, which is still O(n²) because we drop the constant factor and lower-order term. The rule is always the same: identify the term that grows fastest and discard everything else.
Recursive algorithms require a different approach. Consider binary search: each recursive call halves the input and does constant work, giving the recurrence T(n) = T(n/2) + O(1). This solves to O(log n). Merge sort splits the input in half but does O(n) work to merge, giving T(n) = 2T(n/2) + O(n), which solves to O(n log n). You do not need to memorize these — the pattern is to write the recurrence, then either expand it, use the Master Theorem, or draw a recursion tree to see how the total work accumulates across levels. The key insight is that dividing the problem in half at each step is the signature of logarithmic depth, while doing linear work at each level multiplies that depth by n.
In practice, Big-O analysis is a starting point, not the final answer. Two O(n log n) sorting algorithms — merge sort and quicksort — have very different real-world performance because quicksort has better cache behavior and smaller constant factors. An O(n) algorithm with a constant factor of 1000 will lose to an O(n log n) algorithm for inputs under about 10,000. The power of Big-O is in ruling out bad choices at scale: if your dataset has a billion elements, no O(n²) algorithm is viable regardless of constant factors, while O(n log n) is comfortable. Use Big-O to narrow the field, then benchmark the survivors on your actual data and hardware.