Measuring efficiency: Big O
Big O notation describes how an algorithm's running time or memory grows as the input gets larger. It lets us compare algorithms independently of particular computers.
Why not just time it
Actual running time depends on the computer, the language, and other programs. Computer scientists instead count basic steps as a function of the input size n and focus on how that count grows as n becomes large. The key question is: if the input doubles, what happens to the work?
Big O notation
Big O gives an upper bound on growth, ignoring constant factors and smaller terms. An algorithm taking 3n^2 + 5n + 2 steps is O(n^2), because for large n the n^2 term dominates. Big O usually describes the worst case, though average cases are also studied.
Common growth rates
From fastest to slowest growth: O(1) constant, such as reading an array element by index; O(log n) logarithmic, such as binary search; O(n) linear, such as linear search; O(n log n), such as merge sort; O(n^2) quadratic, such as checking every pair; O(2^n) exponential, such as trying every subset; and O(n!) factorial, such as trying every ordering.
What the differences mean
For n = 1,000: log2(n) is about 10, n log2(n) about 10,000, n^2 a million, and 2^n has over 300 digits. A quadratic algorithm that is fine for 1,000 items may be unusable for 10 million. Choosing a better algorithm usually matters far more than buying a faster computer.
Analysing code
A single loop over n items is typically O(n). Two nested loops over n are typically O(n^2). A loop that halves the problem each time is O(log n). Sequential steps add, and the largest term dominates: an O(n) step followed by an O(n^2) step is O(n^2) overall.
Space complexity
Algorithms also use memory. Space complexity measures how extra memory grows with input size. Merge sort uses O(n) extra space; in-place algorithms aim for O(1) or O(log n). Sometimes we trade space for time, such as storing previously computed results to avoid recomputing them.
Related notations
Big O is an upper bound. Big Omega gives a lower bound, and Big Theta means both, a tight bound. Informally, people often say 'Big O' when they mean the tight bound. A proven result: any sort that works only by comparing items needs at least on the order of n log n comparisons in the worst case.
Worked example
A function checks whether a list has duplicates by comparing every pair: two nested loops, about n^2 / 2 comparisons, so O(n^2). For 100,000 items that is about 5 billion comparisons. A better approach sorts first (O(n log n)) then checks neighbours (O(n)), giving O(n log n) overall: roughly 1.7 million steps. Using a hash set gives O(n) on average.
Key takeaways
Efficiency is measured by how step counts grow with input size n. Big O ignores constants and lower terms, usually describing the worst case. Common classes are O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), and O(n!). Algorithm choice matters more than hardware speed for large inputs. Nested loops suggest O(n^2); halving suggests O(log n). Space complexity measures memory. Comparison sorts need on the order of n log n comparisons.
Flashcard
Upper bound on growth rate
Check your understanding
An algorithm takes 4n^2 + 100n + 7 steps. What is its Big O?