Time and Space Complexity
Complexity lets us compare algorithms without depending on one computer or programming language. It tells us how a solution scales.
What Complexity Measures
Timing code with a stopwatch tells you about one machine, one compiler, one input, and whatever else that machine was doing. Run the same program on a faster laptop and every number changes. Complexity analysis exists to say something that survives all of that.
It measures how the cost grows as the input grows, counting the operations an algorithm performs as a function of the input size n, and ignoring everything machine-specific. An algorithm that doubles its work when the input doubles behaves that way on every computer that will ever exist.
That focus on growth is why constants are discarded. An algorithm doing 3n + 50 operations is written O(n), because for large n the multiplier and the offset are irrelevant next to the shape of the growth. Similarly n² + 1000n is O(n²) — the quadratic term overtakes the linear one, and beyond some input size nothing else matters.
The practical consequence is worth internalising. An O(n log n) algorithm beats an O(n²) one on large inputs regardless of constants: for a million elements, roughly 20 million operations against a trillion. No amount of micro-optimisation closes that gap, which is why choosing the right algorithm dominates tuning the wrong one.
The honest caveat is the other side of the same coin: complexity says nothing about small inputs. Insertion sort is O(n²) and beats merge sort on arrays of ten or twenty elements, because its constants are tiny. Real sorting libraries exploit this, switching to insertion sort for small partitions. Big-O describes the trend, not the speed.
- Measures growth with input size, independent of hardware
- Constants and lower-order terms are dropped — only the shape remains
- O(n log n) beats O(n²) at scale no matter the constants
- Says nothing about small inputs, where constants decide
O, Omega, and Theta
Three notations describe different claims, and using the wrong one is a common exam deduction even when the reasoning is right.
Big-O — O(f(n)) — is an upper bound. It says the algorithm grows no faster than f(n), beyond some input size. Saying merge sort is O(n²) is technically true and useless, in the same way that saying a person is under nine feet tall is true. An upper bound need not be tight.
Big-Omega — Ω(f(n)) — is a lower bound. It says the algorithm grows at least as fast as f(n). Comparison-based sorting is Ω(n log n), meaning no comparison sort can do better — a statement about the problem rather than about any one algorithm.
Big-Theta — Θ(f(n)) — is a tight bound, holding when the upper and lower bounds match. Merge sort is Θ(n log n): it is never faster and never slower than that shape.
In practice people say 'big-O' while meaning Θ, and that convention is accepted almost everywhere — but the distinction is worth being able to state, because exam questions test it directly.
A separate axis is which case is being described, and this is genuinely independent of the notation. Best case is the most favourable input, average case the expected behaviour over typical inputs, and worst case the least favourable. Quicksort is Θ(n log n) average and Θ(n²) worst; saying 'quicksort is O(n log n)' without qualification is imprecise.
Worst case is the default in most analysis, because it is the only bound that guarantees anything. Average-case results also require assuming a distribution of inputs, which is often unstated and sometimes wrong.
One more distinction: amortised cost is the average over a sequence of operations, not over random inputs. Appending to a dynamic array is amortised O(1) — most appends are constant, one occasionally copies everything, and the average across n appends is constant. That is a guarantee about the total, not about any single call.
| Notation | Meaning | Example |
|---|---|---|
| O(f) | Grows no faster than f — upper bound | Merge sort is O(n²), technically true |
| Ω(f) | Grows at least as fast as f — lower bound | Comparison sorting is Ω(n log n) |
| Θ(f) | Both bounds match — tight | Merge sort is Θ(n log n) |
| Amortised | Average over a sequence of operations | Dynamic array append |
- O is an upper bound and need not be tight; Θ is the tight one
- Ω often describes the problem, not a particular algorithm
- Best, average and worst case are a separate axis from the notation
- Amortised averages over a sequence, not over random inputs
Reading Complexity Off Code
Analysis is mostly a small set of composition rules applied to the structure of the code.
Sequential blocks add, and the larger dominates. A loop over n followed by another loop over n is O(n) + O(n) = O(n), not O(2n).
Nested loops multiply. Two loops each running n times give O(n²); three give O(n³). But read the bounds carefully — an inner loop running to i rather than n executes n(n+1)/2 times in total, which is still O(n²) but half the work, and an inner loop with a fixed bound contributes only a constant factor.
Halving gives a logarithm. A loop that divides its range each iteration runs about log₂ n times, which is where binary search's O(log n) comes from. A loop that halves inside a linear loop gives O(n log n).
Recursion needs a recurrence. Express the cost as T(n) in terms of smaller calls: merge sort is T(n) = 2T(n/2) + O(n), giving O(n log n); binary search is T(n) = T(n/2) + O(1), giving O(log n). The Master Theorem solves the common shapes directly, and drawing the recursion tree — how much work per level, times how many levels — works when it does not apply.
Two traps deserve naming because they hide real costs. Operations that look constant may not be. String concatenation in an immutable-string language copies everything, so building a string in a loop is O(n²) rather than O(n). Slicing an array copies it. list.pop(0) in Python shifts every element. A loop is only O(n) if its body is genuinely O(1).
And know your library's complexities. Calling contains on a list inside a loop is O(n²); the same code with a set is O(n). Most accidental quadratic behaviour comes from a library call whose cost was assumed rather than checked.
| Complexity | Name | Typical source |
|---|---|---|
| O(1) | Constant | Array index, hash lookup |
| O(log n) | Logarithmic | Binary search, balanced tree operations |
| O(n) | Linear | A single pass over the input |
| O(n log n) | Linearithmic | Merge sort, heap sort — the sorting bound |
| O(n²) | Quadratic | Nested loops over the input |
| O(2ⁿ) | Exponential | Subsets, naive recursion without memoisation |
| O(n!) | Factorial | Permutations, brute-force travelling salesman |
- Sequential blocks add; nested loops multiply
- A loop that halves its range contributes a log factor
- Recursion needs a recurrence — or draw the recursion tree
- Check library call costs; hidden O(n) operations cause accidental O(n²)
Terms, operations, and practical uses
Growth rates
- O(1)Constant. The work does not grow with the input at all.
- O(log n)Logarithmic. Each step discards a fixed fraction of what remains.
- O(n)Linear. Work is proportional to the input size.
- O(n log n)Linearithmic. The best a comparison sort can achieve.
- O(n²)Quadratic. Two nested passes over the same input.
- O(2ⁿ) and O(n!)Exponential and factorial. Every subset, or every permutation. Feasible only for very small n.
Analysis rules
- Sequential workAdd separate costs and retain the fastest-growing term.
- Nested workMultiply loop counts when one loop runs completely inside another.
- Worst caseDescribe the most work required by a valid input.
- O, Ω, ΘO is an upper bound, Ω a lower bound, Θ both at once. Saying Big-O usually means Θ in practice.
- Amortised costThe average per operation across a long sequence. A dynamic array append is O(1) amortised even though one append in many is O(n).
Practical examples
- Array indexingReading a known array position is O(1).
- Linear searchAn unsuccessful search may inspect all n values.
- Binary searchA valid comparison discards half of the remaining ordered range.
Count the work: O(1), O(log n), O(n), O(n²) on the same input
data = [10, 20, 30, 40, 50, 60, 70, 80]
target = 70
# O(1) · one address computation, no search
def constant_lookup(a):
return a[5], 1
# O(log n) · halve the range each comparison
def binary_search(a, x):
lo, hi, steps = 0, len(a) - 1, 0
while lo <= hi:
mid = (lo + hi) // 2
steps += 1
if a[mid] == x:
return mid, steps
if a[mid] < x:
lo = mid + 1
else:
hi = mid - 1
return -1, steps
# O(n) · one comparison eliminates one candidate
def linear_search(a, x):
for i, v in enumerate(a):
if v == x:
return i, i + 1
return -1, len(a)
# O(n^2) · the inner loop restarts for every outer step
def count_pairs(a):
ops = 0
for i in range(len(a)):
for j in range(len(a)):
ops += 1
return ops
_, c1 = constant_lookup(data)
_, c2 = binary_search(data, target)
_, c3 = linear_search(data, target)
c4 = count_pairs(data)
print(f"{c1} operation · {c2} comparisons · {c3} comparisons · {c4} operations")
#include <iostream>
#include <vector>
using namespace std;
// O(1) — one address computation, no search
int constantLookup(const vector<int>& a, int& ops) {
ops = 1;
return a[5];
}
// O(log n) — halve the range each comparison
int binarySearch(const vector<int>& a, int x, int& steps) {
int lo = 0, hi = (int)a.size() - 1;
steps = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
steps++;
if (a[mid] == x) return mid;
if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// O(n) — one comparison eliminates one candidate
int linearSearch(const vector<int>& a, int x, int& steps) {
for (int i = 0; i < (int)a.size(); i++) {
steps = i + 1;
if (a[i] == x) return i;
}
steps = (int)a.size();
return -1;
}
// O(n^2) — the inner loop restarts for every outer step
int countPairs(const vector<int>& a) {
int ops = 0;
for (size_t i = 0; i < a.size(); i++)
for (size_t j = 0; j < a.size(); j++) ops++;
return ops;
}
int main() {
vector<int> data = {10, 20, 30, 40, 50, 60, 70, 80};
int target = 70, c1 = 0, c2 = 0, c3 = 0;
constantLookup(data, c1);
binarySearch(data, target, c2);
linearSearch(data, target, c3);
int c4 = countPairs(data);
cout << c1 << " operation · " << c2 << " comparisons · "
<< c3 << " comparisons · " << c4 << " operations\n";
}class Main {
static int steps = 0;
// O(log n) — halve the range each comparison
static int binarySearch(int[] a, int x) {
int lo = 0, hi = a.length - 1;
steps = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
steps++;
if (a[mid] == x) return mid;
if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// O(n) — one comparison eliminates one candidate
static int linearSearch(int[] a, int x) {
for (int i = 0; i < a.length; i++) {
steps = i + 1;
if (a[i] == x) return i;
}
steps = a.length;
return -1;
}
// O(n^2) — the inner loop restarts for every outer step
static int countPairs(int[] a) {
int ops = 0;
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a.length; j++) ops++;
return ops;
}
public static void main(String[] args) {
int[] data = {10, 20, 30, 40, 50, 60, 70, 80};
int target = 70;
int c1 = 1; // O(1) — one address computation
binarySearch(data, target);
int c2 = steps;
linearSearch(data, target);
int c3 = steps;
int c4 = countPairs(data);
System.out.println(c1 + " operation · " + c2 + " comparisons · "
+ c3 + " comparisons · " + c4 + " operations");
}
}Step through it
Running on Sorted array of 8 values, find 70
Read all 14 Steps
- Eight sorted values The same input, searched three ways. Count the comparisons each method needs and the complexity classes stop being abstract.
- O(1) — read index 5 Reading a known position costs one operation. It would still cost one operation if the array held eight million values, because the address is computed, not searched. That is what constant time means.
- O(log n) — binary search, step 1 Now find 70 without knowing where it is. Look at the middle, index 3, holding 40. One comparison.
- O(log n) — step 2 70 is greater than 40 and the array is sorted, so the whole left half is eliminated. Four values gone from one comparison. Middle of what remains is index 5, holding 60.
- O(log n) — step 3 70 is greater than 60, so discard again. Two candidates remain, and the next comparison finds 70 at index 6. Three comparisons for eight values.
- Why log n barely grows Each comparison halves the search space, so the count is log₂(n). Doubling the array to 16 values adds one comparison, not eight. A million values need twenty.
- O(n) — linear search, start Remove the sorted guarantee and binary search is invalid. Now every element must be checked, starting at index 0.
- O(n) — still scanning Each step eliminates exactly one candidate instead of half of them. No comparison tells you anything about the elements you have not seen.
- O(n) — found at index 6 Seven comparisons for the same lookup binary search did in three. Had 70 been absent, all eight would have run. Work grows in direct proportion to input size.
- O(n²) — compare every pair Some algorithms need every pair: duplicate detection by brute force, bubble sort, comparing all points. For each of 8 elements, scan all 8 — that is 64 operations from an input of 8.
- O(n²) — the second pass Element 2 against all 8 again. The outer loop has advanced by one and the inner loop has restarted. Nested loops multiply, they do not add.
- Why n² breaks down At n = 1,000 that is a million operations — fine. At n = 1,000,000 it is a trillion, which is hours of CPU time. The same code that felt instant in testing becomes unusable in production, and nothing about the code changed except the input.
- The numbers side by side For n = 8: constant 1, logarithmic 3, linear 8, quadratic 64. For n = 1,000,000: 1, 20, 1,000,000, and 1,000,000,000,000. The gaps do not narrow as inputs grow — they explode.
- Space follows the same rules Memory is measured identically. A loop with a few variables is O(1) auxiliary space no matter the input size; copying the input into a new array is O(n); a recursion that nests n deep pays O(n) in stack frames even when it allocates nothing itself.
Space, and What Counts
Space complexity measures memory as a function of input size, and it is analysed the same way — but with one convention that must be stated.
Auxiliary space is the extra memory an algorithm allocates, excluding the input itself. Total space includes the input. Since the input has to exist regardless, auxiliary space is what is normally meant, and it is why an in-place sort is described as O(1) space despite operating on an O(n) array.
Common results follow directly. Merge sort needs an O(n) temporary buffer for merging. Heap sort and in-place quicksort need O(1) for the data, though quicksort's recursion adds O(log n) of stack. A hash set built over the input is O(n).
Recursion consumes stack space equal to its depth, and the distinction between depth and call count is the point most often missed. Naive Fibonacci makes exponentially many calls but is only n frames deep at any instant, because the left branch fully returns before the right begins — so it is O(2ⁿ) time and O(n) space.
For tree algorithms, depth is the tree's height: about 20 frames for a balanced million-node tree, and a million frames for a degenerate one, which overflows the stack. This is precisely why iterative traversals with an explicit stack exist.
There is a genuine trade between time and space, and recognising it is often how a problem gets solved. Memoisation spends O(n) memory to turn exponential time into linear. A hash set spends O(n) memory to turn a nested-loop O(n²) search into a single O(n) pass. Two-sum is the canonical example: sort and use two pointers for O(n log n) time and O(1) space, or use a hash map for O(n) time and O(n) space.
A last practical note: complexity describes growth, and cache behaviour describes speed. Two O(n) algorithms can differ by an order of magnitude if one reads memory sequentially and the other chases pointers. When two approaches tie asymptotically, the one with better locality usually wins — which is a reminder that this analysis is a guide to scaling, not a substitute for measurement.
- Auxiliary space excludes the input and is what is normally quoted
- Recursion costs O(depth), which is not the same as the call count
- Memoisation and hash sets buy time with memory — a deliberate trade
- Equal complexity does not mean equal speed; locality decides