Big O Notation

How to measure and compare the efficiency of algorithms as input grows

Computer Science Algorithms intermediate 8 min

This concept builds on Sorting — Putting Things in Order, Binary Search. Consider exploring them first for the best experience.

Step 1 of 6

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

Step 1 of 6
  1. 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. 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. 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. 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. 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. 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.

Added
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.