Complexity Analysis
Prerequisites: Module 1; comfort with sums and logarithms (Module 3 revisits the maths).
What you will learn
How to measure time and space growth independent of a particular machine.
Big-O, Big-Ω and Big-Θ, and how to derive costs from loops and recurrences.
Amortized analysis, lower bounds, and why measurements still matter.
Prerequisites: Module 1; comfort with sums and logarithms (Module 3 revisits the maths).
2.1 Input size and resource measurement
Use n for element count, V for vertices, E for edges, and m for a second input length. Measure time in operations and space in memory growth, rather than relying only on machine-specific seconds.
2.2 Best, average, expected, and worst case
Best case: most favorable input.
Worst case: maximum cost among inputs of a given size.
Average case: expected cost under a specified input distribution.
Amortized analysis: average cost per operation over a sequence, without requiring random inputs.
Linear search for a value: best case 1 comparison (it is first), worst case n (absent or last), average (n+1)/2 if the target is present and equally likely to be at any position.
2.3 Asymptotic notation
O(g(n)): asymptotic upper bound.
Ω(g(n)): asymptotic lower bound.
Θ(g(n)): tight asymptotic bound.
o(g(n)), ω(g(n)): strict asymptotic bounds.
Formally, f(n) = O(g(n)) if there are constants c > 0 and n₀ with f(n) ≤ c·g(n) for all n ≥ n₀. Example: 3n² + 10n + 7 = O(n²) with c = 4 and n₀ = 11, because 10n + 7 ≤ n² once n ≥ 11.
Common growth order: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!).
Try it: growth rates
complexity2.4 Time versus space complexity
Auxiliary space: extra working memory, often excluding input storage.
Total space: input plus extra storage.
In-place: uses a small or constant amount of extra storage under the stated definition.
Recursion stack: must be counted when recursive calls are active.
2.5 Complexity of common code patterns
The program counts how many times the innermost statement executes for each pattern, so the formulas can be checked rather than trusted:
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
For nested loops, inspect how the bounds depend on each other. A loop that doubles i inside a linear loop is not automatically O(n²); derive the sum. Here the doubling loop runs ⌈log₂ n⌉ times per outer iteration, giving n·log₂ n in total, and the “pairs” loop runs exactly n(n−1)/2 times — half of n², but still Θ(n²).
#include <bits/stdc++.h>
using namespace std;
int main() {
for (long long n : {16, 1024, 1000000}) {
long long linear = 0, logarithmic = 0, nlogn = 0, quadratic = 0, triangle = 0;
for (long long i = 0; i < n; ++i) ++linear; // O(n)
for (long long i = 1; i < n; i *= 2) ++logarithmic; // O(log n)
for (long long i = 0; i < n; ++i)
for (long long j = 1; j < n; j *= 2) ++nlogn; // O(n log n)
if (n <= 1024) {
for (long long i = 0; i < n; ++i)
for (long long j = 0; j < n; ++j) ++quadratic; // O(n^2)
for (long long i = 0; i < n; ++i)
for (long long j = i + 1; j < n; ++j) ++triangle; // n(n-1)/2, still O(n^2)
}
cout << "n=" << n << " linear=" << linear << " log=" << logarithmic << " nlogn=" << nlogn;
if (n <= 1024) cout << " n^2=" << quadratic << " pairs=" << triangle << " (n(n-1)/2=" << n * (n - 1) / 2 << ")";
cout << '\n';
}
}n=16 linear=16 log=4 nlogn=64 n^2=256 pairs=120 (n(n-1)/2=120)
n=1024 linear=1024 log=10 nlogn=10240 n^2=1048576 pairs=523776 (n(n-1)/2=523776)
n=1000000 linear=1000000 log=20 nlogn=200000002.6 Recurrence relations
Model recursive cost with recurrences, then solve by expansion, recursion tree, substitution, or Master Theorem when applicable.
Binary search: T(n) = T(n/2) + O(1) = O(log n).
Merge sort: T(n) = 2T(n/2) + O(n) = O(n log n).
Naive Fibonacci: T(n) = T(n-1) + T(n-2) + O(1), exponential growth.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The call count is 2·fib(n+1) − 1 — it grows like φⁿ ≈ 1.618ⁿ. Memoisation (Module 22) turns the same recurrence into O(n) work.
#include <bits/stdc++.h>
using namespace std;
long long calls = 0;
long long fib(int n) { // naive recursion
++calls;
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
int main() {
for (int n : {10, 20, 30}) {
calls = 0;
long long f = fib(n);
cout << "fib(" << n << ") = " << f << " using " << calls << " calls\n";
}
// memoized: each value computed once
vector<long long> memo(91, -1);
function<long long(int)> mfib = [&](int n) -> long long {
if (n < 2) return n;
if (memo[n] != -1) return memo[n];
return memo[n] = mfib(n - 1) + mfib(n - 2);
};
cout << "memoized fib(90) = " << mfib(90) << '\n';
}fib(10) = 55 using 177 calls
fib(20) = 6765 using 21891 calls
fib(30) = 832040 using 2692537 calls
memoized fib(90) = 28800671943708161202.7 Master Theorem
For T(n) = aT(n/b) + f(n), compare f(n) with n^(log_b a). Teach the standard cases and regularity conditions; do not apply the theorem blindly to unequal subproblems or nonstandard recurrences.
f(n) = O(n^(log_b a − ε)) for some ε > 0 Θ(n^(log_b a)) T(n) = 8T(n/2) + n² → Θ(n³) f(n) = Θ(n^(log_b a)) Θ(n^(log_b a) · log n) merge sort, 2T(n/2) + n → Θ(n log n)
f(n) = Ω(n^(log_b a + ε)) and a·f(n/b) ≤ c·f(n) for some c < 1 T(n) = 2T(n/2) + n² → Θ(n²)
Binary search has a = 1, b = 2, so n^(log_2 1) = 1 = Θ(f(n)): case 2 gives Θ(log n). Recurrences like T(n) = T(n/3) + T(2n/3) + n (unequal parts) need a recursion tree or the Akra–Bazzi method instead.
2.8 Amortized analysis
Dynamic-array append: occasional resizing costs O(n), but append is O(1) amortized over a sequence.
The program watches std::vector grow and counts element copies caused by reallocation:
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
With libstdc++ the capacity doubles, so the total copying work is 1 + 2 + 4 + … + 512 < 1024: fewer than one copy per append on average. That is the aggregate-method proof that append is O(1) amortized, even though a single append can cost O(n). The growth factor is implementation-defined (other libraries use 1.5); any constant factor greater than 1 gives the same amortized bound.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v;
size_t lastCap = v.capacity(), copies = 0;
cout << "capacity changes:";
for (int i = 0; i < 1000; ++i) {
size_t before = v.size();
v.push_back(i);
if (v.capacity() != lastCap) {
copies += before; // a reallocation moves every existing element
lastCap = v.capacity();
cout << ' ' << lastCap;
}
}
cout << "\nappends: 1000, element copies from resizing: " << copies
<< " (" << fixed << setprecision(3) << copies / 1000.0 << " per append)\n";
}capacity changes: 1 2 4 8 16 32 64 128 256 512 1024
appends: 1000, element copies from resizing: 1023 (1.023 per append)2.9 Lower bounds and trade-offs
Explain comparison sorting's Ω(n log n) lower bound, time-space trade-offs, preprocessing versus query speed, and why asymptotic complexity does not replace profiling.
Comparison-sort lower bound: any comparison sort can be drawn as a binary decision tree whose leaves are the n! possible orderings. A binary tree with n! leaves has height at least log₂(n!) = Θ(n log n), so some input needs that many comparisons.
Preprocessing versus query: sorting once (O(n log n)) lets every later search be O(log n); for a single search, a linear scan is cheaper.
Constants and caches: an O(n log n) algorithm with poor memory locality can lose to an O(n²) insertion sort for small n — which is why real sort implementations switch to insertion sort for short ranges (Module 18).
Edge cases and common mistakes
Dropping a term that is not dominated: O(n + m) cannot be simplified to O(n) unless m = O(n).
Forgetting the recursion stack when stating space.
Treating O as “exactly”: O(n²) is an upper bound; an O(n) algorithm is also O(n²).
Quoting average case without stating the input distribution.
Required exercises: classify single/double/nested logarithmic loops; solve recurrences; compare algorithms at small and large n; identify misleading complexity claims.
Practice
Easy: give the complexity of for (i = n; i > 0; i /= 2) for (j = 0; j < i; ++j). (Hint: the inner work sums to n + n/2 + n/4 + … < 2n.)
Medium: solve T(n) = 3T(n/2) + n with the Master Theorem.
Hard: show that an algorithm doing n dynamic-array appends with growth factor 1.5 still performs O(n) total copies.
Quiz
? What is the complexity of `for (i = 0; i < n; ++i) for (j = 1; j < n; j *= 2) work();`?
- O(n²) :: The inner loop doubles `j`, so it runs about log n times.
+ O(n log n) :: n outer iterations × about log₂ n inner iterations — the program counted 1024 × 10 = 10240 for n = 1024.
- O(log n) :: The outer loop is linear.
- O(n) :: The inner loop is not constant.
? `std::vector::push_back` sometimes copies every element. Why is it still O(1)?
+ Amortized: capacity grows geometrically, so total copying over n appends is O(n). :: The run showed fewer than 1.03 copies per append.
- It never copies. :: Reallocation moves the elements.
- The copies happen in another thread. :: No.
- Because copying is cheap. :: The bound is about counts, not hardware speed.
? Which recurrences can the Master Theorem solve directly? (select all that apply)
+ T(n) = 2T(n/2) + n :: Case 2, Θ(n log n).
+ T(n) = T(n/2) + 1 :: Case 2, Θ(log n).
- T(n) = T(n/3) + T(2n/3) + n :: Unequal subproblems — use a recursion tree or Akra–Bazzi.
- T(n) = T(n−1) + 1 :: Not of the form aT(n/b) + f(n).Related topics
Module 3 (logarithms and sums), Module 18 (sorting lower bound in practice), Module 22 (memoisation), Module 56 (cache effects).