15.20 Complexity Analysis
You have a divide-and-conquer algorithm and need to analyze its running time and memory usage.
15.20 Complexity Analysis
Problem
You have a divide-and-conquer algorithm and need to analyze its running time and memory usage.
The code may look simple:
solve(input)
split input
solve left
solve right
combine
but the actual cost depends on several details:
- How many subproblems are created?
- How large are the subproblems?
- How expensive is the combine step?
- How deep is the recursion?
- How much auxiliary memory is allocated?
- Are subproblems balanced or uneven?
How do you analyze divide-and-conquer complexity systematically?
Solution
Translate the algorithm into a recurrence, then solve the recurrence.
Most divide-and-conquer algorithms have a cost model of the form:
$$ T(n)=aT(n/b)+f(n) $$
where:
- (a) is the number of recursive calls
- (n/b) is the size of each recursive subproblem
- (f(n)) is the work outside recursion
- (T(n)) is the total running time
Once the recurrence is known, use recursion trees, the Master Theorem, substitution, or direct expansion.
The analysis should also include space complexity, not only time.
Step 1: Identify the Recursive Calls
Start with the recursive structure.
Example:
func MergeSort(a []int) []int {
if len(a) <= 1 {
return a
}
mid := len(a) / 2
left := MergeSort(a[:mid])
right := MergeSort(a[mid:])
return Merge(left, right)
}
There are two recursive calls.
Each call receives roughly half the input.
So the recursive part is:
$$ 2T(n/2) $$
Step 2: Identify the Non-Recursive Work
For merge sort, the non-recursive work is the merge step.
Merging two sorted arrays of total length (n) costs:
$$ O(n) $$
Therefore:
$$ T(n)=2T(n/2)+O(n) $$
This solves to:
$$ O(n\log n) $$
Step 3: Check the Base Case
A recurrence must stop.
For merge sort:
n <= 1
The base case costs:
$$ O(1) $$
So the complete recurrence is:
$$ T(n)= \begin{cases} O(1), & n \le 1 \\n2T(n/2)+O(n), & n>1 \end{cases} $$
The base case usually does not change the asymptotic result, but it matters for correctness and termination.
Common Recurrence Patterns
| Algorithm | Recurrence | Time |
|---|---|---|
| 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)) |
| Karatsuba | (T(n)=3T(n/2)+O(n)) | (O(n^{1.585})) |
| Strassen | (T(n)=7T(n/2)+O(n^2)) | (O(n^{2.807})) |
| Bad quick sort | (T(n)=T(n-1)+O(n)) | (O(n^2)) |
| Quickselect average | (T(n)=T(n/2)+O(n)) | (O(n)) |
These patterns cover many practical algorithms.
Recursion Tree Method
The recursion tree shows work level by level.
For:
$$ T(n)=2T(n/2)+n $$
the tree has:
| Level | Nodes | Work per Node | Total Work |
|---|---|---|---|
| 0 | 1 | (n) | (n) |
| 1 | 2 | (n/2) | (n) |
| 2 | 4 | (n/4) | (n) |
| (k) | (2^k) | (n/2^k) | (n) |
There are:
$$ \log_2 n $$
levels.
Total:
$$ n\log n $$
The method is visual, direct, and often sufficient.
Master Theorem Method
For recurrences of the form:
$$ T(n)=aT(n/b)+f(n) $$
compare (f(n)) with:
$$ n^{\log_b a} $$
Example:
$$ T(n)=3T(n/2)+n $$
The critical term is:
$$ n^{\log_2 3} $$
Since:
$$ n $$
is smaller than:
$$ n^{\log_2 3} $$
the recursive leaves dominate.
Result:
$$ T(n)=O(n^{\log_2 3}) $$
This is the Karatsuba recurrence.
Direct Expansion
Some recurrences do not fit the Master Theorem.
Example:
$$ T(n)=T(n-1)+n $$
Expand:
$$ T(n)=T(n-1)+n $$
$$ T(n-1)=T(n-2)+(n-1) $$
So:
$$ T(n)=T(n-2)+(n-1)+n $$
Continuing:
$$ T(n)=1+2+3+\cdots+n $$
Thus:
$$ T(n)=O(n^2) $$
This is the quick sort worst case.
Uneven Recurrences
Some algorithms split unevenly.
Example:
$$ T(n)=T(n/3)+T(2n/3)+O(n) $$
This does not fit the simple Master Theorem because the subproblem sizes differ.
A recursion tree helps.
At each level, the total problem size across nodes remains (n).
The depth is still:
$$ O(\log n) $$
because the largest branch shrinks by a constant factor.
Therefore:
$$ T(n)=O(n\log n) $$
This style appears in some selection, geometry, and partitioning algorithms.
Quick Sort Complexity
Quick sort is useful because it has multiple complexity stories.
Best Case
Balanced partition:
$$ T(n)=2T(n/2)+O(n) $$
Result:
$$ O(n\log n) $$
Average Case
Random pivot:
$$ O(n\log n) $$
Expected time.
The exact recurrence involves averaging over all pivot positions, but the result remains:
$$ O(n\log n) $$
Worst Case
Pivot is always smallest or largest:
$$ T(n)=T(n-1)+O(n) $$
Result:
$$ O(n^2) $$
The same algorithm has three different analyses depending on pivot behavior.
Quickselect Complexity
Quickselect also depends on partition quality.
Good Split
$$ T(n)=T(n/2)+O(n) $$
Expansion:
$$ n + n/2 + n/4 + \cdots $$
This sums to:
$$ O(n) $$
Bad Split
$$ T(n)=T(n-1)+O(n) $$
This gives:
$$ O(n^2) $$
Randomization gives expected:
$$ O(n) $$
Median of medians gives worst-case:
$$ O(n) $$
but with larger constants.
Space Complexity
Time is only half the analysis.
Divide-and-conquer algorithms also consume stack space and sometimes auxiliary buffers.
Recursion Stack
If recursion depth is:
$$ d $$
and each frame costs:
$$ O(1) $$
then stack space is:
$$ O(d) $$
Examples:
| Algorithm | Depth | Stack Space |
|---|---|---|
| Binary search | (O(\log n)) | (O(\log n)) recursive, (O(1)) iterative |
| Merge sort | (O(\log n)) | (O(\log n)) stack |
| Balanced quick sort | (O(\log n)) | (O(\log n)) stack |
| Worst-case quick sort | (O(n)) | (O(n)) stack |
Auxiliary Memory
Some algorithms allocate memory proportional to the input.
Merge sort typically needs:
$$ O(n) $$
extra space for merging.
Quick sort typically uses:
$$ O(\log n) $$
stack space on average and sorts in place.
FFT uses:
$$ O(n) $$
space for transform arrays.
A complexity analysis should state both:
time complexity
space complexity
not just one.
Allocation Patterns
Be careful with recursive allocation.
This version creates many temporary arrays:
left := append([]int(nil), a[:mid]...)
right := append([]int(nil), a[mid:]...)
Even if the asymptotic space is still manageable, allocation overhead can dominate runtime.
Production implementations often pass index ranges and reuse buffers.
The algorithmic recurrence may be correct, but the implementation cost can be worse than expected.
Balanced vs Unbalanced Recursion
Balanced recursion:
n -> n/2 and n/2
has depth:
$$ O(\log n) $$
Unbalanced recursion:
n -> 1 and n-1
has depth:
$$ O(n) $$
This affects both time and stack space.
When analyzing recursive code, always ask:
How small is the largest recursive child?
That determines the height of the recursion tree.
Cost of Splitting
Splitting is sometimes free and sometimes expensive.
Free or cheap:
left := a[:mid]
right := a[mid:]
This creates slice views.
Expensive:
left := copyOf(a[:mid])
right := copyOf(a[mid:])
This copies data.
If every recursive call copies its input, the recurrence changes.
Always include splitting cost when it is nontrivial.
Cost of Combining
The combine step often determines the final complexity.
Examples:
| Algorithm | Combine Cost |
|---|---|
| Binary search | (O(1)) |
| Merge sort | (O(n)) |
| Closest pair | (O(n)) |
| Strassen | (O(n^2)) |
| FFT | (O(n)) |
| Bad recursive algorithms | sometimes (O(n^2)) |
A divide step is usually simple.
The combine step is where performance is won or lost.
Amortized Perspective
Some divide-and-conquer algorithms perform work that appears expensive locally but is cheap across a level.
Example:
merge sort copies n elements per level
Each element participates in one merge per level.
There are:
$$ O(\log n) $$
levels.
So each element contributes:
$$ O(\log n) $$
total merge work.
This element-level perspective can be easier than solving a recurrence.
Lower-Order Terms
In asymptotic analysis, we often simplify:
$$ T(n)=2T(n/2)+3n+17 $$
to:
$$ T(n)=2T(n/2)+O(n) $$
This is valid for Big O notation.
However, lower-order terms and constants matter in engineering.
Karatsuba beats grade-school multiplication only beyond a threshold.
Strassen beats classical multiplication only for sufficiently large matrices.
Parallel algorithms can be slower for small inputs.
Asymptotic analysis predicts growth. Benchmarking determines practical cutoffs.
Common Mistakes
Counting Recursive Calls but Not Combine Work
For merge sort, saying:
two recursive calls, so O(log n)
is wrong.
The merge step costs (O(n)) at each level.
Assuming Balanced Splits
Quick sort is not always balanced.
Worst-case behavior must be analyzed separately.
Ignoring Copy Costs
Copying slices, strings, or matrices at every level may add hidden work.
Confusing Stack Space and Auxiliary Space
Merge sort uses (O(\log n)) stack but (O(n)) merge buffer.
State both.
Applying the Master Theorem Blindly
The basic Master Theorem does not handle every recurrence.
Unequal subproblem sizes and variable branching require other tools.
Discussion
Complexity analysis for divide-and-conquer algorithms is a process, not a formula. Start by reading the code structurally. Count recursive calls. Measure subproblem sizes. Account for splitting and combining. Then solve the recurrence using the simplest valid method.
The most common failure is leaving out a cost that appears harmless in the code. Copying a slice, building a strip, merging two arrays, or allocating temporary matrices can determine the final bound. A good analysis includes those costs explicitly.
At the same time, asymptotic analysis is only the first pass. Real performance depends on cache behavior, allocation, constants, branch prediction, and parallel scheduling. The recurrence tells you how the algorithm scales. Measurement tells you where the implementation crosses from theory into practice.