Skip to interview prep
Apexed

60. Explain the substitution method by proving T(n) = 2T(n/2) + n is O(n log n).

MediumAlgorithm analysis

Technical
Show model answer

Guess the form of the answer, then prove it by induction, choosing constants so the inductive step works. Guess T(n) <= c·n log n for n >= 2. Assume it holds for n/2. Then T(n) <= 2·c(n/2)log(n/2) + n = c·n log n - c·n + n, which is <= c·n log n whenever c >= 1 (logs base 2).

Then check base cases (for example n = 2 and n = 3) and pick c large enough to cover them. A common trap is proving T(n) <= cn + n and calling it O(n): the induction must reproduce the exact hypothesis, not a slightly bigger expression. If it does not, strengthen the guess by subtracting a lower-order term, such as cn - d.

Explain the substitution method by proving T(n) = 2T(n/2) + n is O(n log n). — Data structures & algorithms interview question — Apexed