What is Big O Notation?
Big O notation describes how an algorithm's running time grows as the input size grows.
It answers the question: if I double the input, how much slower does my algorithm get?
Big O strips away the hardware, the language, and the constant factors. It only cares about the dominant growth pattern — what happens when your input gets large. This makes it a universal language for comparing algorithms.
The "O" stands for "order of" — as in, "the order of growth is..."
Why We Ignore Constants
You might wonder: if one algorithm does 2n operations and another does 100n, why do we call them both O(n)?
Because as n gets large, the constant factor matters less and less. If n = 1,000,000:
2n = 2,000,000100n = 100,000,000
Yes, that's a 50x difference. But compare it to an O(n²) algorithm at the same n:
n² = 1,000,000,000,000(one trillion)
The O(n) algorithms, regardless of their constants, are both orders of magnitude faster than O(n²). Big O is about the shape of growth, not the exact number.
The Common Complexities
O(1) — Constant Time
No matter how large the input, the operation takes the same time.
Accessing an array by index is O(1). The array could have 5 elements or 5 million — the lookup time doesn't change.
O(log n) — Logarithmic Time
Each step cuts the remaining work in half. Doubling the input only adds one more step.
Binary search on a sorted array: check the middle, discard half, repeat.
O(log n) algorithms are remarkably fast at scale.
O(n) — Linear Time
One step per element. Doubling the input doubles the time.
Scanning an unsorted array to find an element is O(n) — in the worst case you check every element.
O(n log n) — Linearithmic Time
Slightly worse than linear, much better than quadratic. Most efficient sorting algorithms land here.
Merge sort, quick sort (average case), and heap sort are all O(n log n). This is often the best you can do for a comparison-based sort.
O(n²) — Quadratic Time
A nested loop over the input. Every element is compared with every other element.
O(n²) is fine for small inputs (n < 1000). For large inputs, it becomes too slow. If your algorithm has two nested loops both iterating over the input, start suspecting O(n²).
O(2^n) — Exponential Time
Doubles with every added element. Common in naive recursive solutions without memoization.
The naive recursive Fibonacci is a classic example:
Memoization (Dynamic Programming) fixes this to O(n).
O(n!) — Factorial Time
The worst. Generating all permutations of n elements.
Brute-force solutions to the Travelling Salesman Problem run in O(n!). In practice, you'd never run this on large inputs.
Complexity Comparison at a Glance
| Complexity | n = 10 | n = 100 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | 3 | 7 | 10 | 20 |
| O(n) | 10 | 100 | 1,000 | 1,000,000 |
| O(n log n) | 33 | 664 | 10,000 | 20,000,000 |
| O(n²) | 100 | 10,000 | 1,000,000 | 10¹² |
| O(2^n) | 1,024 | 10³⁰ | 10³⁰¹ | — |
How to Calculate Time Complexity
Rule 1: Drop constants
3n + 5 → O(n)
Rule 2: Drop lower-order terms
n² + n + 100 → O(n²)
Rule 3: Sequential steps add
Rule 4: Nested loops multiply
Rule 5: Halving at each step → logarithmic
Best, Average, and Worst Case
Big O typically describes the worst case — the hardest input your algorithm might face.
- Best case (Ω notation): the easiest possible input
- Average case (Θ notation): a typical random input
- Worst case (O notation): the hardest possible input
For linear search: best case is O(1) (target at index 0), worst case is O(n) (target at the end or not present). When someone says "linear search is O(n)," they mean the worst case.
Quick sort is O(n log n) average but O(n²) worst case (when the pivot is always the smallest or largest element). This is why pivot selection matters.