Big O Notation
How to measure and compare the efficiency of algorithms as input grows
This concept builds on Sorting — Putting Things in Order, Binary Search. Consider exploring them first for the best experience.
What Big O measures
Big O notation describes how an algorithm's work grows as the input size n grows. It keeps only the dominant term and drops constant factors, so 2n + 5 operations is simply O(n). On the canvas each coloured curve is one growth class. The dashed n marker sweeps from left to right, and beside it every curve prints its operation count at that n.
O(1) and O(log n) — nearly flat
Drag the 'n marker' to 16, then to 32. The O(1) readout stays at 1, like reading one slot of an array. O(log n) goes from 4 to 5 — one extra step each time n doubles, like binary search, where a billion sorted items need only about 30 halvings. Both hug the bottom of the plot; press 'Log scale' to space the axis in powers of ten and watch them separate.
O(n) and O(n log n) — manageable
Toggle the 'Curves' buttons O(n²) and O(2ⁿ) off: the axis zooms in on the remaining curves. Now drag the 'n marker' along the plot. At n = 16 the O(n) and O(n log n) readouts are 16 and 64; at n = 32 they are 32 and 160. O(n) is a single pass over a list; O(n log n) is the cost of the best general comparison sorts, such as merge sort.
O(n²) and O(2ⁿ) — the danger zone
Turn both curves back on with the 'Curves' buttons and drag the 'n marker' to 20. O(n²) reads 400 — nested loops checking every pair, like bubble sort. O(2ⁿ) reads 1.0 × 10⁶, the 1,048,576 ways to choose a subset of 20 items. On the linear axis the purple curve leaves the top almost at once; with 'Log scale' on it becomes a straight, steep line — the signature of exponential growth.
The doubling test
To recognise a growth class, ask what happens when the input doubles. With the marker at 20, press 'Show 2n': a second cursor appears at 40 and each curve gets a vertical jump to its new value. O(n) goes from 20 to 40 and O(n²) from 400 to 1,600 — four times as many — while O(2ⁿ) leaps from about 10⁶ to 1.1 × 10¹². The note under each card gives the factor.
Worked Example: Which sort for n = 10⁶?
You must sort a million records. Bubble sort is O(n²): n² = 10¹² comparisons. Merge sort is O(n log n): log₂ 10⁶ is about 20, so n log₂ n ≈ 2 × 10⁷. At 10⁸ simple operations per second that is 10,000 seconds — nearly 3 hours — against 0.2 seconds. The plot stops at 100, but the gap already shows there: set 'n max' to 100, drag the 'n marker' to the right edge and compare 10,000 with 664.
How It Works — Step by Step
-
1
What Big O measures
Big O notation describes how an algorithm's work grows as the input size n grows. It keeps only the dominant term and drops constant factors, so 2n + 5 operations is simply O(n). On the canvas each coloured curve is one growth class. The dashed n marker sweeps from left to right, and beside it every curve prints its operation count at that n.
-
2
O(1) and O(log n) — nearly flat
Drag the 'n marker' to 16, then to 32. The O(1) readout stays at 1, like reading one slot of an array. O(log n) goes from 4 to 5 — one extra step each time n doubles, like binary search, where a billion sorted items need only about 30 halvings. Both hug the bottom of the plot; press 'Log scale' to space the axis in powers of ten and watch them separate.
-
3
O(n) and O(n log n) — manageable
Toggle the 'Curves' buttons O(n²) and O(2ⁿ) off: the axis zooms in on the remaining curves. Now drag the 'n marker' along the plot. At n = 16 the O(n) and O(n log n) readouts are 16 and 64; at n = 32 they are 32 and 160. O(n) is a single pass over a list; O(n log n) is the cost of the best general comparison sorts, such as merge sort.
-
4
O(n²) and O(2ⁿ) — the danger zone
Turn both curves back on with the 'Curves' buttons and drag the 'n marker' to 20. O(n²) reads 400 — nested loops checking every pair, like bubble sort. O(2ⁿ) reads 1.0 × 10⁶, the 1,048,576 ways to choose a subset of 20 items. On the linear axis the purple curve leaves the top almost at once; with 'Log scale' on it becomes a straight, steep line — the signature of exponential growth.
-
5
The doubling test
To recognise a growth class, ask what happens when the input doubles. With the marker at 20, press 'Show 2n': a second cursor appears at 40 and each curve gets a vertical jump to its new value. O(n) goes from 20 to 40 and O(n²) from 400 to 1,600 — four times as many — while O(2ⁿ) leaps from about 10⁶ to 1.1 × 10¹². The note under each card gives the factor.
-
6
Worked Example: Which sort for n = 10⁶?
You must sort a million records. Bubble sort is O(n²): n² = 10¹² comparisons. Merge sort is O(n log n): log₂ 10⁶ is about 20, so n log₂ n ≈ 2 × 10⁷. At 10⁸ simple operations per second that is 10,000 seconds — nearly 3 hours — against 0.2 seconds. The plot stops at 100, but the gap already shows there: set 'n max' to 100, drag the 'n marker' to the right edge and compare 10,000 with 664.
Key Takeaways
Constants don't matter; growth rate does
O(1000n) is still O(n). For small n the constant factor matters, but as n grows large, an O(n log n) algorithm will always beat an O(n²) one — no matter how small the n² constant is.
Double the input to diagnose the class
When n doubles, O(1) work stays the same, O(log n) adds one step, O(n) doubles, O(n²) quadruples and O(2ⁿ) squares. Timing a program at n and 2n reveals which class it is in.
Space complexity works the same way
Big O applies to memory too. An in-place sort uses O(1) extra space. Merge sort needs O(n) extra space for the merge step. Trade-offs between time and space complexity are central to algorithm design.
The common complexities ranked
From best to worst: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). Most practical problems have efficient algorithms in O(n) to O(n log n) — recognising when you're accidentally writing O(n²) code is a key engineering skill.
Connected Concepts
Sorting
Bubble sort is O(n²); merge sort is O(n log n). Big O explains why the choice of sorting algorithm matters enormously for large inputs.
Binary Search
Binary search is O(log n) — each comparison halves the problem. Big O makes this performance guarantee precise.
Recursion
Recursive algorithms' time complexity is analysed using recurrence relations, which simplify to Big O expressions.
Hash Table
A hash table finds a key in O(1) average time by jumping straight to its bucket, instead of scanning all n entries.
Logarithms
log₂ n counts how many times n can be halved before reaching 1 — exactly the number of steps an O(log n) search takes.
Exponential Functions
O(2ⁿ) is an exponential function of the input size: every extra item doubles the work, which is why it becomes a straight line on a log scale.
Dynamic Programming
Storing answers to repeated subproblems can turn an O(2ⁿ) recursive search into an O(n) or O(n²) table fill.
Amortized Analysis
A single array push can cost O(n) when it resizes, yet averaged over n pushes each one costs O(1).
Updated
- — New connection to Amortized Analysis.
- — Drag the n marker to read every curve, plus a worked example: which sort to use for a million records.