Methods for solving recurrences

Three methods to solve a recurrence such as T(n) = 2T(n/2) + n:

1. Substitution method: guess the form of the solution (e.g. T(n) = O(n log n)) and prove it by mathematical induction.
2. Recursion-tree method: draw the tree of recursive calls, find the cost at each level, and sum over all levels. For the example, each level costs n and there are log n levels, giving Θ(n log n).
3. Master theorem: for T(n) = aT(n/b) + f(n), compare f(n) with n^(log_b a) to get the answer directly. Here a = 2, b = 2, f(n) = n = n^1, so T(n) = Θ(n log n).

(Iteration/back-substitution, expanding repeatedly, is another form of the first method.)