Complexity Analysis

A recursive algorithm's running time is governed by a recurrence relation — T(n) expressed in terms of T applied to smaller inputs — and solving that recurrence, not eyeballing the code, is what yields the true asymptotic bound, because recursive cost stacks non-linearly across levels of self-similar subcalls.

Recognize the pattern

• A function calls itself on one or more smaller inputs (e.g. n/2, n-1, n-k).
• You're asked for time/space complexity of something that isn't a simple loop — merge sort, binary search, Fibonacci, quicksort, tree traversal.
• Counting "how many recursive calls" naively gives wrong answers — e.g. binary search makes only log n calls, not n, because each call halves the input.
• The problem mentions "divide and conquer" or the recursion branches into multiple sub-calls per level.

The recurrence relation

General form: T(n) = a·T(n/b) + f(n), where a is the number of subproblems per call, n/b is the size of each subproblem, and f(n) is the work done outside the recursive calls (dividing input + combining results). The base case, e.g. T(1) = Θ(1), is where recursion bottoms out.

Example: merge sort splits an array into 2 halves and spends O(n) merging them → T(n) = 2T(n/2) + O(n).

Brute force vs. optimal derivation

Brute force (manual unrolling): expand T(n) → T(n/2) → T(n/4) … term by term until a pattern emerges, then sum the resulting series. It always works but is slow, error-prone on depth/off-by-one, and impractical for anything with an ugly f(n).

Optimal — pick the matching technique:

Complexity derived from first principles

Take T(n) = 2T(n/2) + cn (merge sort). Build the recursion tree and count total work level by level:

• Level 0 (root): 1 node, problem size n, cost cn.
• Level 1: 2 nodes, each size n/2, cost c(n/2) each → total 2·c(n/2) = cn.
• Level i: 2ⁱ nodes, each size n/2ⁱ, cost c(n/2ⁱ) each → total 2ⁱ·c(n/2ⁱ) = cn.
• Every level costs exactly cn — the divide-halves + O(n)-merge cancel out.
• Depth: recursion stops when n/2ⁱ = 1, i.e. i = log₂n levels.

Total time = (work per level) × (number of levels) = cn · log2(n) = Θ(n log n). This matches Master Theorem Case 2 (a=2, b=2, f(n)=Θ(n^{log_b a}) = Θ(n¹)).

Space is a separate axis: it is the max depth of the call stack × space per frame, not the total nodes in the tree. Merge sort's deepest single active path is O(log n) frames, but each merge step also allocates O(n) auxiliary array space at various points — net auxiliary space is O(n) (dominated by the merge buffers), call-stack space is O(log n).

Traced worked example

T(n) = 2T(n/2) + n, with n = 8 (using c = 1 for simplicity):

Depth = log2(8) = 3 → 4 levels (0..3). Total = 8 × 4 = 32 = n·(log2 n + 1), confirming Θ(n log n).

Pitfalls

• Forgetting f(n) is not constant — treating T(n)=2T(n/2)+n like T(n)=2T(n/2)+O(1) (which is only Θ(n), a classic Master Theorem Case 1 mix-up).
• Misapplying the Master Theorem when a is not a positive integer ≥1, b≤1, or f(n) isn't polynomially comparable to n^{log_b a} (e.g. f(n)=n/log n needs the extended/Akra–Bazzi form, not vanilla Master Theorem).
• Confusing call-stack space with total work done — O(n) total nodes in a tree does not mean O(n) auxiliary stack space; stack space is bounded by the deepest single root-to-leaf path.
• For unbalanced recursion (e.g. quicksort worst case T(n)=T(n-1)+O(n)), assuming balanced-tree depth log n when the real depth is n.

When to use which technique

Master theorem: fastest when the recurrence is already in aT(n/b)+f(n) form and one of the three cases cleanly applies — O(1) to apply, but doesn't cover unequal subproblem sizes or non-polynomial gaps.

Recursion tree: use when subproblem sizes are unequal (e.g. T(n)=T(n/3)+T(2n/3)+n) or you need intuition/a guess to verify — more visual but more manual bookkeeping.

Substitution (induction): use when you already suspect a bound and need a rigorous proof, or the recurrence has extra terms Master Theorem can't handle — most rigorous but requires a correct guess up front.

Trade-off in one line: Master theorem trades generality for speed; recursion tree and substitution trade speed for generality and rigor.

Recurrence shapes worth memorizing: T(n)=T(n-1)+O(1) → Θ(n) time and Θ(n) stack (linear recursion); T(n)=T(n-1)+O(n) → Θ(n²) (quicksort worst case); T(n)=T(n/2)+O(1) → Θ(log n) (binary search); T(n)=2T(n/2)+O(n) → Θ(n log n) (merge sort); T(n)=T(n-1)+T(n-2)+O(1) → Θ(φⁿ) time with Θ(n) stack (naive Fibonacci — the left spine, not the node count, sets the depth).

Takeaways

• Every recursive algorithm has a recurrence T(n)=aT(n/b)+f(n); solving it, not counting calls by intuition, gives the real bound.
• The recursion tree method sums per-level work times the number of levels — this is literally how Θ(n log n) for merge sort is derived, not asserted.
• Time and space are separate: total tree work drives time, but max stack depth (a single root-to-leaf path) drives space.
• Pick Master theorem for speed on standard forms, recursion tree/substitution when subproblems are unequal or the bound needs proof.

Recall: For T(n) = 3T(n/2) + n, what is the per-level work at level i, and what is the overall time complexity?

Synthesized from standard recurrence-analysis treatments (CLRS Master Theorem & recursion-tree method) and the source page's recursion tree walkthrough.