Computer Science

Solving the Divide and Conquer Recurrence

An exploration of the recurrence relation T(n) = 2T(n/2) + n, demonstrating how to use substitution and normalization to find a closed form and asymptotic complexity.

Scene 1 of 5

Defining the Problem

T(n) = 2T(n/2) + n

Let's look at the recurrence relation T(n) = 2T(n/2) + n, which describes algorithms that split a problem in two and perform linear work at each step. Given T(1) = 1, how do we find a closed form for any n that is a power of 2?

Step-by-step solver

(a) Transformation

Substitute n = 2^k to rewrite the recurrence in terms of the exponent k.

T(2^k) = 2T(2^{k-1}) + 2^k

(b) Normalization

Divide the entire recurrence by 2^k to reduce it to a simple additive form S(k) = S(k-1) + 1.

\frac{T(2^k)}{2^k} = \frac{T(2^{k-1})}{2^{k-1}} + 1

Use the initial condition S(0) = T(1)/1 = 1 to solve the arithmetic recurrence S(k) = k + 1.

S(k) = 1 + k

(d) Back-Substitution

Substitute S(k) = T(n)/n and k = log2(n) to obtain the final closed-form expression.

T(n) = n(\log_2 n + 1)

(e) Asymptotics

Identify the dominant term as n log n, leading to the asymptotic class.

T(n) = \Theta(n \log n)

Original question

Solve the recurrence relation T(n) = 2 T(n/2) + n for n a power of 2, with T(1) = 1. Find a closed form for T(n) and state the asymptotic complexity.

Follow-up chat

Ask me anything about this lesson — I'll answer using what we just covered.