Big O Notation Explained With Real Code Examples
A practical explanation of Big O — what O(1), O(log n), O(n), O(n log n) and O(n²) mean, how to work out the complexity of your own code, and the hidden linear operations that make innocent-looking loops slow.
By Software Side Hustles Editorial Team · Published · Updated · 5 min read
Quick answer: Big O describes how the work an algorithm does grows as its input grows, ignoring constant factors. O(1) is constant regardless of size, O(n) grows in proportion to the input, O(n²) grows with the square of it. It matters because the difference between O(n) and O(n²) is invisible on 100 items and decisive on 1,000,000.
The common complexities
| Big O | Name | Example | Operations for n = 1,000,000 |
|---|---|---|---|
| O(1) | Constant | Read arr[i], look up a key in a hash map | 1 |
| O(log n) | Logarithmic | Binary search in a sorted array | ~20 |
| O(n) | Linear | Loop over every item once | 1,000,000 |
| O(n log n) | Linearithmic | Efficient sorting (Timsort, merge sort) | ~20,000,000 |
| O(n²) | Quadratic | Compare every item with every other item | 1,000,000,000,000 |
| O(2ⁿ) | Exponential | Try every subset; naive recursive Fibonacci | astronomically large |
At a billion simple operations per second, the O(n log n) column finishes in a fraction of a second. The O(n²) column takes over a quarter of an hour.
O(1): constant time
def first(items): return items[0]
prices = {"apple": 0.5}prices["apple"] # hash lookup: O(1) on averageThe work does not depend on how big items or prices is. "Constant" does not mean "fast" — it means "does not grow".
O(n): linear time
def total(items): s = 0 for x in items: s += x return sOne pass, one unit of work per item. Double the input, double the time.
O(n²): quadratic time
def has_duplicates(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return FalseA loop inside a loop over the same data. With a set, the same question becomes O(n):
def has_duplicates(items): return len(set(items)) != len(items)Trading memory (the set) for time is one of the most common optimisations in practice.
O(log n): logarithmic time
Each step halves the remaining work. Binary search on a sorted list of a million items needs about 20 comparisons, because 2²⁰ ≈ 1,000,000:
import bisecti = bisect.bisect_left(sorted_ids, target)found = i < len(sorted_ids) and sorted_ids[i] == targetBalanced trees and database B-tree indexes give O(log n) lookups for the same reason — which is why adding the right index turns a slow query into a fast one.
O(n log n): sorting
Comparison-based sorting cannot do better than O(n log n) in general, and the built-in sorts in Python, Java and JavaScript achieve it. If you sort inside a loop, though, you multiply: sorting once per item is O(n² log n).
How to work out the complexity of your code
- Count loops over the input. One loop: O(n). Nested loops over the same input: O(n²). Sequential loops: O(n) + O(n) = still O(n).
- Drop constants and smaller terms. O(3n + 50) is O(n). O(n² + n) is O(n²).
- Use different letters for different inputs. Looping over
usersand, inside, overordersis O(u × o), not O(n²). - Look inside the loop body for hidden costs. This is where most real-world slowness comes from.
Hidden O(n) operations inside loops
These look like single steps but scan or copy the whole collection:
| Operation | Cost | Faster alternative |
|---|---|---|
x in some_list (Python), arr.includes(x) (JS) | O(n) | use a set / Set: O(1) |
list.pop(0), list.insert(0, x) (Python) | O(n) | collections.deque: O(1) at both ends |
arr.shift() / arr.unshift() (JS) | O(n) | index pointer, or a proper queue |
ArrayList.remove(0) (Java) | O(n) | ArrayDeque |
LinkedList.get(i) (Java) | O(n) | ArrayList for random access |
s = s + piece in a loop (Python, Java) | O(n) copy per step | "".join(parts), StringBuilder |
arr.indexOf(x) / list.index(x) | O(n) | a dict/map from value to index |
| A database query inside a loop (N+1 queries) | n round trips | one query with JOIN or IN |
A loop of n iterations containing any of these is O(n²) — even though there is only one visible loop.
Space complexity
Big O also describes memory. Building a set of all items is O(n) extra space; reversing an array in place with two pointers is O(1) extra space. Recursion uses stack space proportional to its depth, which is how stack overflow errors happen.
Average, worst case and amortised
- Hash maps are O(1) on average, but O(n) in the worst case when many keys collide. Real implementations make that worst case very unlikely.
- Appending to a dynamic array (
list.append,ArrayList.add,arr.push) is amortised O(1): occasionally the array has to grow and copy everything, but averaged over many appends each costs a constant amount. - Quicksort is O(n log n) on average and O(n²) in the worst case, which is why libraries use variants or other algorithms with better guarantees.
When Big O does not matter
For small inputs, constants dominate: a simple O(n²) loop over 20 items can beat a clever O(n log n) algorithm with more overhead. Readability matters too. Optimise when the input can be large or the code runs often — and measure with a profiler, not guesses.
Frequently asked questions
What is the difference between Big O, Big Theta and Big Omega?
Strictly, Big O is an upper bound, Omega a lower bound and Theta a tight bound. In everyday engineering conversation, "Big O" is used to mean the tight bound for the case being discussed.
Is O(2n) the same as O(n)?
Yes. Constant factors are dropped because they do not change how the cost grows.
What is the Big O of a dictionary lookup?
O(1) on average for hash-based dictionaries (Python dict, JavaScript Map, Java HashMap). Tree-based maps such as Java's TreeMap are O(log n).
How do I improve an O(n²) algorithm?
Usually by precomputing a lookup structure (a set or map), sorting first so you can use two pointers or binary search, or reducing repeated work with caching.
Where this skill pays off
Complexity analysis is one of the main criteria for judging AI-generated solutions — is the "clever" answer actually faster, and does the stated complexity match the code? Try our free linear vs binary search and nested-loop exercises, and read what makes one coding solution better than another.