Big-O and Complexity Analysis
Measure how an algorithm's cost grows with input size, read common complexity classes at a glance, and reason about time, space, and amortized cost.
beginner40 min#big-o#complexity#time#space#amortized
Prerequisites: How to Study Programming
Why it matters
Two programs can both give the right answer, yet one finishes in a blink and the other outlives the universe once the input grows. Big-O gives you a shared vocabulary for that difference. It lets you compare solutions before writing them, spot the bottleneck in a design, and answer the question every interviewer asks: "what is the complexity?"
Intuition
Do not time your program in seconds; seconds depend on the laptop, the language, and the weather. Instead ask: if the input gets ten times bigger, how much more work happens?
- Finding a name in an unsorted guest list means checking each name: ten times the guests, ten times the work. That is linear.
- Finding a word in a dictionary by opening to the middle and discarding half each time: a million words need only about 20 steps. Ten times the words add roughly 3 steps. That is logarithmic.
- Introducing every guest to every other guest: ten times the guests, a hundred times the handshakes. That is quadratic.
Big-O keeps only the shape of that growth and throws away constants and lower-order terms, because for large inputs the shape dominates.
How it works
Say f(n) is the number of basic steps for an input of size n. We write f(n) = O(g(n)) when, beyond some point, f never grows faster than a constant multiple of g. In practice you apply three rules.
- Drop constants:
3nand100nare bothO(n). - Drop lower-order terms:
n^2 + 5n + 40isO(n^2). - Add sequential parts, multiply nested parts: two loops one after the other cost
O(n) + O(n) = O(n); a loop inside a loop costsO(n * n).
Common classes, fastest to slowest:
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
n = 1,000,000 steps (roughly)
O(log n) 20
O(n) 1,000,000
O(n log n) 20,000,000
O(n^2) 1,000,000,000,000
| Operation | Time | Notes |
|---|---|---|
| Array index a[i] | O(1) | Constant, independent of n |
| Binary search in sorted array | O(log n) | Halve the range each step |
| Scan a list once | O(n) | Touch each item |
| Efficient sort (merge, heap) | O(n log n) | Best possible for comparison sorts |
| Compare every pair | O(n^2) | Nested loops over the same input |
| All subsets of n items | O(2^n) | Exponential; only tiny n |
Beyond the worst case
- Best, average, worst: linear search finds its target at once in the best case (
O(1)), but we normally quote the worst case (O(n)) because it is a guarantee. - Big-Theta and Big-Omega:
Ois an upper bound,Omegaa lower bound, andThetameans both, a tight bound. In casual conversation people say "O(n)" and mean the tight bound. - Amortized cost: an operation that is usually cheap but occasionally expensive can still average out. Appending to a doubling dynamic array is
O(1)amortized because the rareO(n)resize is paid for by many cheap appends. - Space complexity: the same analysis for extra memory. A recursive function that goes
ncalls deep usesO(n)stack space even if it allocates nothing else.
Reading complexity from code
- A single loop over
nitems doing constant work:O(n). - A loop where the variable doubles or halves (
i *= 2):O(log n). - A loop inside a loop, both over
n:O(n^2). If the inner loop starts ati + 1, the total is aboutn^2 / 2, stillO(n^2). - Two independent inputs, sizes
aandb: writeO(a + b)orO(a * b), never collapse them into onen. - Recursion that splits into two halves and does linear work to combine (merge sort):
O(n log n).
Code: counting steps
Rather than trust the rules, count steps. This program counts how many comparisons a linear search and a binary search take to miss a value in a sorted list, and how many pair visits a double loop makes.
def linear_search(a, target):
steps = 0
for i, x in enumerate(a):
steps += 1
if x == target:
return i, steps
return -1, steps
def binary_search(a, target):
lo, hi, steps = 0, len(a) - 1, 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
if a[mid] == target:
return mid, steps
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1, steps
def count_pairs_quadratic(a):
steps = 0
for i in range(len(a)):
for j in range(i + 1, len(a)):
steps += 1
return steps
for n in (1000, 1000000):
a = list(range(n))
print(n, "linear", linear_search(a, -1)[1], "binary", binary_search(a, -1)[1])
print("pairs for n=1000:", count_pairs_quadratic(list(range(1000))))function linearSearch(a, target) {
let steps = 0;
for (let i = 0; i < a.length; i++) {
steps++;
if (a[i] === target) return [i, steps];
}
return [-1, steps];
}
function binarySearch(a, target) {
let lo = 0, hi = a.length - 1, steps = 0;
while (lo <= hi) {
steps++;
const mid = Math.floor((lo + hi) / 2);
if (a[mid] === target) return [mid, steps];
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return [-1, steps];
}
function countPairsQuadratic(a) {
let steps = 0;
for (let i = 0; i < a.length; i++) {
for (let j = i + 1; j < a.length; j++) steps++;
}
return steps;
}
for (const n of [1000, 1000000]) {
const a = Array.from({ length: n }, (_, i) => i);
console.log(n, "linear", linearSearch(a, -1)[1], "binary", binarySearch(a, -1)[1]);
}
console.log("pairs for n=1000:", countPairsQuadratic(Array.from({ length: 1000 }, (_, i) => i)));Both versions print:
1000 linear 1000 binary 9
1000000 linear 1000000 binary 19
pairs for n=1000: 499500
A thousand times more data made linear search a thousand times slower but binary search only about two times slower (9 to 19 steps). The pair count, 1000 * 999 / 2, shows the quadratic blow-up.
To feel the difference, here are both searches on the same sorted array of 9 items, looking for 72 (the last one).
Linear search needs 9 comparisons here, binary search only 4. With a million items the gap becomes 1,000,000 versus about 20.
Common pitfalls
- Hidden costs in built-ins:
x in my_listisO(n), string concatenation in a loop can beO(n^2), slicing copies. Know what the library call costs. - Confusing average with worst case: a hash table lookup is
O(1)on average butO(n)if every key collides. Quicksort isO(n log n)on average andO(n^2)in its worst case. - Treating two inputs as one: iterating a grid with
rrows andccolumns isO(r * c), notO(n^2)unless the grid is square. - Forgetting recursion space: the call stack counts. Recursing to depth
nisO(n)memory. - Counting only loops:
sorted(...)inside a loop turns an apparentO(n)intoO(n^2 log n).
Practice
Classify these snippets easy
Hint
Count how the loop variable changes and whether loops are nested or sequential.
Show solution
(a) for i in range(n): for j in range(n): work() is O(n^2). (b) i = n; while i > 1: i //= 2 runs about log2(n) times, so O(log n). (c) A loop over n followed by a separate loop over n is O(n + n) = O(n). (d) for i in range(n): for j in range(i): work() does 0 + 1 + ... + (n-1) = n(n-1)/2 steps, O(n^2).
Does the order of ops matter? medium
Hint
Compare sorting then scanning against checking every pair for a duplicate.
Show solution
To find whether a list has duplicates, checking every pair is O(n^2) time and O(1) space. Sorting first costs O(n log n) and then neighbors are compared in O(n), so O(n log n) overall (space depends on the sort). A set gives O(n) time and O(n) space. Each choice trades time for memory; state the trade-off aloud.
Amortized analysis of a counter medium
Hint
How often does bit 0 flip? Bit 1? Bit k?
Show solution
Incrementing a binary counter from 0 to n flips bit k about n / 2^k times. The total flips are n * (1 + 1/2 + 1/4 + ...), below 2n. So the amortized cost per increment is O(1) even though a single increment, such as 0111 to 1000, can flip many bits.
Find the complexity of recursive Fibonacci hard
Hint
Draw the call tree for fib(5). How many calls does each level produce?
Show solution
fib(n) calls fib(n-1) and fib(n-2), so the number of calls roughly multiplies by about 1.6 each level, which is O(2^n) as a simple upper bound (tight bound about 1.618^n). The tree recomputes the same values again and again. Memoizing each fib(k) once reduces the work to O(n) time and O(n) space, which is the idea behind dynamic programming.
Interview questions
- What does O(n log n) mean in plain words? Work grows a bit faster than linear: for each of
nitems you do aboutlog nwork, typical of divide-and-conquer such as merge sort. - Why do we drop constants? For large
ngrowth rate dominates, and constants depend on hardware and language. They still matter when comparing two algorithms of the same class. - Time and space: which do you optimize? Ask about constraints. Often you trade one for the other (hash set versus sort).
- What is amortized O(1)? An average over a sequence of operations that guarantees constant cost per operation even though single operations may be expensive.
Interviewers look for: stating the complexity of both time and space without being asked, naming the input variables, and distinguishing average from worst case.
Quick check
An algorithm takes 1 second for n = 1,000. If it is O(n^2), roughly how long for n = 10,000?
Finished this lesson?
Further resources
- Big O notation (Wikipedia) (article)
- Time complexity (Wikipedia) (article)
- Python time complexity of built-ins (docs)