Big-O is the language programmers use to discuss whether an algorithm will still work when the data grows by 10×, 100×, or 1 000×. It is not about timing a function on your laptop — it is about the shape of the growth curve. Once you can read it, you can have an informed opinion about almost any algorithm in any codebase.
What changed in 2026
- LLM-assisted coding makes complexity awareness more important, not less. AI assistants generate O(n²) solutions to problems that have O(n log n) solutions. Recognising the difference is now a core developer skill.
- Data volumes keep growing. With pgvector embedding tables at 50 M+ rows and event streams at billions of records, choosing O(n log n) over O(n²) is a real-world cost and latency difference.
- Interview culture shifted. FAANG-style whiteboard complexity drills softened, but product companies still filter on "can you spot a nested loop problem?" Practical complexity reasoning matters.
- GPU parallelism does not remove algorithmic complexity. A GPU runs O(n²) faster but the scaling curve is the same. Algorithmic improvements compound on top of hardware.
The seven complexity classes
| Class |
Name |
Example algorithm |
| O(1) |
Constant |
Hash table lookup, array index |
| O(log n) |
Logarithmic |
Binary search, balanced BST |
| O(n) |
Linear |
Linear scan, single loop |
| O(n log n) |
Linearithmic |
Merge sort, heap sort, good sort |
| O(n²) |
Quadratic |
Bubble sort, nested loop comparison |
| O(2^n) |
Exponential |
Naive recursive subset generation |
| O(n!) |
Factorial |
Brute-force travelling salesman |
Everything above O(n log n) is "be careful at scale." Everything above O(n²) is "don't ship to production with large n."
Reading Big-O in real code
O(1) — constant:
lookup = {"alice": 42, "bob": 7}
val = lookup["alice"] # O(1) regardless of dict size
O(n) — single loop:
def find_max(arr):
m = arr[0]
for x in arr: # iterates n times
if x > m:
m = x
return m
O(n²) — nested loop:
def has_duplicate(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)): # inner loop = O(n) × outer O(n)
if arr[i] == arr[j]:
return True
return False
# Fix: use a set → O(n) time, O(n) space
O(log n) — halving the problem:
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1 # discard left half
else:
hi = mid - 1 # discard right half
return -1
Dropping constants and lower-order terms
Big-O deliberately ignores constants because hardware and language differences swamp them at any fixed n. When n grows without bound, only the dominant term matters.
O(3n + 100) → O(n)O(n² + n) → O(n²)O(n log n + n²) → O(n²) (n² dominates)O(500) → O(1)
Space complexity
Every algorithm also has a space complexity — how much extra memory it uses relative to input size.
| Algorithm |
Time |
Space |
| In-place sort (heapsort) |
O(n log n) |
O(1) |
| Merge sort |
O(n log n) |
O(n) |
| Recursive DFS (tree) |
O(n) |
O(h) — h = height |
| Memoised Fibonacci |
O(n) |
O(n) |
| Hash set dedup |
O(n) |
O(n) |
Trading space for time is one of the most common optimisation patterns. See Hash tables explained in 2026 for the canonical example.
How to spot the complexity class
- Count loops. One loop over n → O(n). Two nested loops over n → O(n²). Be careful: a loop inside a recursive call multiplies.
- Check if you discard half the problem each step. Halving → O(log n) component.
- Look for sorts.
Array.sort(), sorted(), .sort() are all O(n log n).
- Check data structure operations. Hash table get/set: O(1). Sorted set insert: O(log n). Array insert at front: O(n).
- Count recursive branches. Two branches with no memoisation → likely O(2^n) or worse.
How to pick the right complexity
- n < 1 000? Almost anything works; pick the readable solution.
- n ~ 10 000–100 000? O(n²) starts to hurt; target O(n log n) or better.
- n > 1 M? O(n log n) is fine; O(n²) is unusable; chase O(n) or O(log n) if possible.
- Is the bottleneck I/O, not CPU? Big-O may not be your problem — profile first.
Common mistakes
Counting the wrong n. If n is the number of nodes and e is the number of edges, graph DFS is O(n + e), not O(n). Identify what "n" refers to precisely.
Ignoring built-in complexity. Python's in on a list is O(n). in on a set is O(1). Swapping them inside a loop can change O(n²) to O(n).
Optimising O(n) to O(n/2) and calling it a win. That is still O(n). Find a genuinely different algorithm.
Conflating average and worst case. Quick sort is O(n log n) average but O(n²) worst case on sorted input. Use sorted() (Timsort) for production — it is O(n log n) worst case.
What to skip
- Premature micro-optimisations inside O(n) code — profiling beats guessing. See How to profile slow code in 2026.
- Hand-rolling O(n log n) sorts — every standard library has Timsort or equivalent; use it.
- Memorising Big-O tables without understanding structure — derive it from the code by counting; you will remember it.
FAQ
What is the difference between O, Ω, and Θ?
Big-O is an upper bound (worst case). Omega (Ω) is a lower bound (best case). Theta (Θ) is a tight bound (both). In interviews and daily work, "Big-O" informally means the tight worst-case bound.
Does O(1) mean fast?
Not necessarily. O(1) means constant-time — the time does not grow with n. That constant could be 1 ms or 500 ms. A slow O(1) operation can dominate a fast O(n) loop for small n.
How do I handle multiple inputs?
Use separate variables. An algorithm that loops over two arrays of sizes n and m is O(n + m), not O(n²).
Is Big-O enough for system design?
No. Big-O ignores cache locality, I/O, concurrency, and network latency. Use it to eliminate obviously bad choices, then measure with real data.
Where to go next