Skip to interview prep
Apexed

3. State the Master Theorem and apply it to merge sort.

MediumAlgorithm analysis

Technical
Show model answer

For recurrences T(n) = aT(n/b) + f(n) with a ≥ 1 and b > 1, compare f(n) with n^(log_b a). If f(n) is polynomially smaller, T(n) = Θ(n^(log_b a)). If they are equal up to log factors (f(n) = Θ(n^(log_b a) logᵏ n)), T(n) = Θ(n^(log_b a) logᵏ⁺¹ n). If f(n) is polynomially larger (and regular), T(n) = Θ(f(n)).

Merge sort: T(n) = 2T(n/2) + Θ(n). Here n^(log₂2) = n, which matches f(n), so T(n) = Θ(n log n). Binary search: T(n) = T(n/2) + Θ(1) gives Θ(log n).

State the Master Theorem and apply it to merge sort. — Data structures & algorithms interview question — Apexed