Big O Notation
Describing growth.
Big O is a short way to describe how an algorithm's steps grow. It sounds scary, but it's just a label. O of N means the steps grow in step with N, the size of the input. You'll see it everywhere, in docs, in interviews, and in code reviews.

- A short label for growth
- O(n): grows with n
- You'll see it everywhere
The main Big O labels
Here are the labels you'll meet most, from fastest to slowest. O of one is constant, the same no matter how big the input. O of log N grows very slowly. O of N grows in step with the input. O of N log N is how good sorting grows. And O of N squared gets slow very quickly.
| Big O | Name | Example |
|---|---|---|
| O(1) | constant | look up a dict key |
| O(log n) | logarithmic | binary search |
| O(n) | linear | loop over a list |
| O(n log n) | linearithmic | good sorting |
| O(n²) | quadratic | nested loops |
Feeling the difference
This code prints how many steps each label means, for a few input sizes. Log two counts how many times you can halve a number. Run it. Look at the last row. For a million items, O of log N is about twenty steps. O of N squared is a million million.
import math
print(f"{'n':>9} {'log n':>6} {'n log n':>12} {'n squared':>16}")
for n in [10, 1_000, 1_000_000]:
print(f"{n:>9,} {math.log2(n):>6.0f} {n * math.log2(n):>12,.0f} {n * n:>16,}") n log n n log n n squared
10 3 33 100
1,000 10 9,966 1,000,000
1,000,000 20 19,931,569 1,000,000,000,000Summary
Big O labels how steps grow. O of one, log N, N, N log N, and N squared. Next, the two simple rules for working out Big O yourself.
Key takeaways- O(1) < O(log n) < O(n)
- O(n log n) < O(n²)
- It describes growth