Measuring Algorithm Growth with Big-O Notation
Byte stands at a giant whiteboard covered in curves — a flat line, a gentle slope, a steep curve, and an almost-vertical rocket line — each labeled with a different algorithm name, marker in hand, circling the one that stays flattest as n climbs toward a million.
- Explain what Big-O notation communicates about an algorithm's growth rate.
- Identify the Big-O class of simple code patterns such as constant, linear, logarithmic, and quadratic loops.
- Compare two algorithms by their Big-O class to predict which scales better for large inputs.
- Predict how runtime changes when input size doubles, for O(1), O(n), O(log n), and O(n²) algorithms.
- Justify why constant factors are ignored when expressing Big-O complexity.
Key terms
- Big-O notation
- An asymptotic upper bound describing how an algorithm's cost grows as input size increases.
- Asymptotic analysis
- Studying algorithm behavior as input size approaches very large values, ignoring small inputs.
- Constant time, O(1)
- Runtime that does not grow with input size, like indexed array access.
- Logarithmic time, O(log n)
- Runtime that grows by one step each time the input doubles.
- Quadratic time, O(n²)
- Runtime that grows with the square of the input size.
Why Constants and Lower Terms Drop
Big-O captures growth rate, not exact step counts, so we discard constant factors and lower-order terms. An algorithm taking 3n + 50 steps is O(n) because, as n grows large, the +50 becomes negligible and the multiplier 3 reflects hardware and language details rather than the algorithm's structure. Formally, f(n) is O(g(n)) if there exist constants c and n0 such that f(n) <= c·g(n) for all n >= n0. This definition deliberately ignores small inputs and scaling constants so two implementations of the same algorithm share one complexity class.
Reading Complexity From Loops
You can usually infer Big-O by inspecting loop structure. A single loop bounded by n contributes O(n); two nested loops each bounded by n multiply to O(n²); independent sequential loops add and the larger term dominates. A loop that halves its working set each pass contributes O(log n), and combining a linear scan with logarithmic work per element yields O(n log n), the class of efficient comparison sorts. Recognizing these shapes lets you predict scaling before running a single benchmark, which is essential when datasets reach millions of items.
Worked examples
Determine the Big-O class of a function with one loop over n followed by two nested loops over n.
- The single loop over n performs n iterations, contributing O(n).
- The two nested loops each run n times, performing n × n = n² iterations, contributing O(n²).
- Add the two parts: total work is n + n², so the cost is O(n + n²).
- Keep only the dominant term as n grows large, since n² eventually overwhelms n.
Answer: O(n²), because the quadratic term dominates the linear term for large n.
Activity
Drag each code snippet to its correct Big-O time complexity bucket on the board.
Practice
State the Big-O class of code that prints every pair of items in a list of n items.
If an O(n) algorithm takes 4 seconds on 1000 items, estimate its time on 4000 items.
Common mistakes to avoid
- O(2n) differs from O(n)Constant multipliers are dropped, so O(2n) and O(n) are the identical complexity class.
- Big-O measures actual secondsBig-O describes how cost grows with input size, not concrete wall-clock runtime on hardware.
Check your understanding
An algorithm has two nested loops, each running from 0 to n. What is its Big-O time complexity?
Algorithm A runs in exactly 100n steps. Algorithm B runs in 2n steps. Which statement best describes their Big-O complexity?
A binary search algorithm halves the remaining search space on every step. If the input doubles from n to 2n, roughly how many extra steps does binary search need?
Recap
Big-O notation expresses how an algorithm's cost grows with input size, dropping constants and lower-order terms to compare structural efficiency. Loop shape reveals common classes from O(1) and O(log n) up through O(n²).
Reflect
Why might an O(n²) algorithm still be the right choice for a tiny, fixed-size dataset?