Big O notation is a way to describe how the work an algorithm does grows as its input gets larger. Instead of measuring exact seconds, which depend on your hardware, it answers a more durable question: if you double the input, does the work stay the same, double, or explode? An algorithm that is O(n) does roughly twice the work for twice the data; one that is O(n squared) does four times the work. Big O is the shared language programmers use to compare approaches before writing a line of code.
Why it ignores the details
Big O deliberately throws away constants and lower-order terms. An algorithm that does 3n + 50 steps is simply O(n), because as n grows huge, the 3 and the 50 stop mattering next to n itself. This feels imprecise, and for tiny inputs it is, but that is the point. Big O is built to answer how something behaves at scale, where the shape of the growth dominates everything else.
This is also why Big O is not a stopwatch. A poorly tuned O(n) routine can lose to a tight O(n squared) one on small inputs. Big O tells you which one wins as the data grows, not which is faster on your laptop today.
The common complexity classes
| Notation |
Name |
Doubling the input means |
Example |
| O(1) |
Constant |
No change |
Array index lookup |
| O(log n) |
Logarithmic |
One more step |
Binary search |
| O(n) |
Linear |
Twice the work |
Scanning a list |
| O(n log n) |
Linearithmic |
Slightly more than double |
Efficient sorting |
| O(n squared) |
Quadratic |
Four times the work |
Nested loops over a list |
| O(2 to the n) |
Exponential |
Roughly squares |
Brute-force subsets |
The order in the table is also the order of preference. Anything at or below O(n log n) usually scales fine; O(n squared) gets uncomfortable in the thousands; exponential is unusable beyond small inputs.
Reading it from code
You can often estimate Big O by counting loops over the input.
// O(1): one operation, no loop over the input
def first(items):
return items[0]
// O(n): one loop over n items
def total(items):
s = 0
for x in items: // runs n times
s += x
return s
// O(n squared): a loop inside a loop, both over n
def has_duplicate(items):
for a in items: // n times
for b in items: // n times each
if a is not b and a == b:
return True
return False
A single pass is linear, a nested pass is quadratic, and repeatedly halving the search space, as binary search does, is logarithmic. The complexity you get often depends on the data structure you chose, since lookups in some are constant and in others linear. Recursion that branches, like generating every subset, tends toward exponential.
Time versus space
Big O describes time complexity, how the number of steps grows, and space complexity, how the extra memory grows. They can differ. Sometimes you trade more memory for less time, like caching results to turn repeated work into a lookup. Stating both is good practice: an algorithm might be O(n) in time and O(1) in space, or vice versa.
How to use Big O in practice
- Identify the input that grows. Big O is always in terms of some
n.
- Find the dominant loop or recursion. That usually sets the class.
- Drop constants and smaller terms.
2n + 100 is O(n).
- Compare alternatives by class before micro-optimizing.
- Sanity-check against real input sizes. If
n is always tiny, readability beats complexity.
Common misconceptions
"Lower Big O is always faster." Only at scale. Constants and real-world factors decide small cases.
"Big O measures my program speed." It measures growth, not wall-clock time; the same class runs at different speeds on different machines.
"Big O is only about the worst case." Big O typically expresses an upper bound, but you can also describe best and average cases; people just usually mean the worst case in casual use.
FAQ
What does the O stand for in Big O?
It stands for "order of," as in the order of growth of the function. The notation comes from mathematics, where it describes how functions behave as their input approaches infinity.
Is O(1) always better than O(n)?
At scale, yes, but for small inputs the difference can be irrelevant, and an O(1) approach that uses huge memory may not be worth it. Context matters.
Do I need Big O for everyday programming?
You rarely calculate it formally, but recognizing when code is accidentally O(n squared) on large data saves real performance problems, so the intuition is worth having.
What is the difference between Big O and Big Theta?
Big O is an upper bound; Big Theta is a tight bound that captures both upper and lower growth. In casual use people say Big O even when they mean the tight bound.
Where to go next
See what is a data structure in 2026, what is a hash table in 2026, and what is a binary tree in 2026.