DataslopeComplexity Analysis
Understand Big-O, Big-Omega, Big-Theta, amortized analysis, and common performance pitfalls
Algorithms are not judged only by whether they work. They are judged by how their resource usage grows. Hardware changes constants; asymptotic growth explains what happens when input size becomes huge.
Why we care
On ten items, almost any correct solution feels instant. On ten million items, an O(n^2) loop can be impossible while an O(n log n) solution still finishes.
Complexity is about growth
Big-O ignores machine speed and focuses on how work changes as input size grows. Constants still matter in real systems, but growth rate decides what is possible at scale.
Big-O, Big-Ω, and Big-Θ
Let f(n) be the work your algorithm does and g(n) be a comparison function such as n, n log n, or n^2.
| Notation | Meaning | Intuition |
|---|---|---|
| Big-O | Upper bound | Grows no faster than this, up to constants. |
| Big-Ω | Lower bound | Grows at least this fast, up to constants. |
| Big-Θ | Tight bound | Both an upper and lower bound. |
Formally, f(n) = O(g(n)) if there exist constants c and n0 such that f(n) <= c*g(n) for all n >= n0.
The sum function is Θ(n): it must inspect every element, and it does constant work per element.
Growth rates hierarchy
| Complexity | Example |
|---|---|
| O(1) | Read v[0] |
| O(log n) | Binary search |
| O(sqrt n) | Trial division up to sqrt(n) |
| O(n) | Scan a vector |
| O(n log n) | Comparison sorting |
| O(n^2) | Check every pair |
| O(2^n) | Try every subset |
| O(n!) | Try every permutation |
Timing small programs is noisy, especially in a browser sandbox, but measurement is useful when paired with complexity analysis.
Reading loops and binary search
A single loop over n items is usually O(n). A nested loop over all pairs is usually O(n^2). Binary search is O(log n) because each comparison halves the remaining search space.
A pair-counting loop runs n(n - 1) / 2 times, which is Θ(n^2).
Amortized analysis
Some operations are occasionally expensive but cheap on average over a sequence. std::vector::push_back is the classic example: most pushes write one element, but when capacity is full, the vector allocates a larger array and moves existing elements.
The doubling argument: if capacity doubles, each element is moved only a small number of times across many insertions. The total work for n pushes is O(n), so each push is O(1) amortized.
Common pitfalls
Ignoring constants: O(100n) and O(n) are the same asymptotic class, but constants can matter for realistic inputs.
Over-emphasizing constants: if n can become large, an O(n^2) design usually loses to O(n log n), even when the quadratic code is short.
Confusing worst, average, and best case: linear search is O(1) in the best case when the first item matches, but O(n) in the worst case when the item is last or missing.
Best case is rarely enough
When a problem asks for complexity, state which case you mean. Interviews and algorithm textbooks often default to worst-case unless otherwise specified.
Practice: counting pairs and duplicates
Implement int countPairs(const std::vector<int>& v, int target) to count pairs (i, j) where i < j and v[i] + v[j] == target.
Use the straightforward O(n^2) nested-loop version for this challenge. Later, you will learn how a hash map can reduce this idea to O(n).
Implement bool hasDuplicate(const std::vector<int>& v) so it returns true if any value appears at least twice.
A naive O(n^2) solution is accepted here. If you already know std::unordered_set, that gives an O(n) average-time approach.
Test your knowledge
Which complexity grows more slowly for large n: O(n log n) or O(n^2)?
O(n log n) grows more slowly
O(n^2) is asymptotically faster
They are the same because both contain n
It depends only on the programming language
What is the time complexity of binary search on a sorted array of length n?
O(1)
O(log n)
O(n)
O(n^2)
What does amortized O(1) mean for std::vector::push_back?
Every single call always performs exactly one machine instruction
Every call is worst-case O(1), even when the vector reallocates
A sequence of many pushes has constant average cost per push, even though occasional pushes are expensive
It means pushing is O(log n) but written differently
For a fixed input size n = 10, is an O(n!) algorithm always slower than an O(2^n) algorithm?
No; asymptotic notation describes growth, and constants/implementation details can dominate at one fixed input size
Yes; Big-O gives exact runtimes for every n
Yes; Big-O rankings give exact runtime order at n = 10
No; O(n!) is always faster than O(2^n)
Key idea