Big-O Race

Big-O describes how the work an algorithm does grows as its input grows. The race shows real operation counts side by side.

Input size n =

O(1)
Constant
0
1 operations
under a microsecond · Array index, HashMap get
O(log n)
Logarithmic
0
10 operations
under a microsecond · Binary search
O(n)
Linear
0
1,000 operations
1 µs · Scan a list once
O(n log n)
Linearithmic
0
10,000 operations
10 µs · Merge sort
O(n²)
Quadratic
0
10,00,000 operations
1 ms · Bubble sort, nested loops
O(2ⁿ)
Exponential
0
≈ 10^301 operations
longer than the age of the universe · All subsets, naive Fibonacci

At n = 1,000, the finishing order is O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ).

O(n²) does 100× the work of O(n log n) here. Bar length uses a logarithmic scale (a bar twice as long means vastly more work, not twice), sized to the polynomial lanes; O(2ⁿ) runs off the chart. Times assume a billion simple operations per second.

What's happening?

Pick an input size and every contestant runs on it at once.
Counts are calculated exactly; the track uses a logarithmic scale so O(1) and O(2ⁿ) fit on one screen.
The time column assumes a billion simple operations per second — roughly one CPU core.

Complexity

Time: Compares O(1) · O(log n) · O(n) · O(n log n) · O(n²) · O(2ⁿ)
Space: —

Where you'll meet it

Choosing between a nested loop and a HashMap, or a sort and a scan, is a Big-O decision — it decides whether a feature works at 10 users or 10 million.

Common mistake

Thinking O(n²) is "a bit slower" than O(n log n). At n = 100,000 it is about 6,000 times more work.

FAQ

What does O(n log n) mean?

The work grows a little faster than the input — like sorting with merge sort.

Is O(1) always fastest?

It does not grow with n, but its constant can still be large; Big-O describes growth, not exact speed.

Why is O(2ⁿ) so bad?

Each extra input doubles the work: n = 60 is already about 10¹⁸ operations.