Final answer:
The recurrence relation T(n) = T(n/2) + 3n with T(1) = 0 is solved by expanding the recurrence, recognizing it forms a geometric series, and calculating the sum to find the closed-form solution T(n) = 6n - 3 for n being a power of 2.
Step-by-step explanation:
To solve the recurrence relation T(n) = T(n/2) + 3n with the initial condition T(1) = 0, we apply the method of iteration. We assume n is a power of 2, specifically n = 2^k, to simplify the problem.
Expanding the recurrence gives us:
- T(n) = T(n/2) + 3n
- T(n/2) = T(n/4) + 3(n/2)
- T(n/4) = T(n/8) + 3(n/4)
- ...
- T(2) = T(1) + 3(2)
Since T(1) = 0, we can see that each step contributes an additional multiple of n. Summing over the total contributions, we get:
T(n) = 3n + 3n/2 + 3n/4 + ... + 3
This forms a geometric series with a common ratio of 1/2. The sum of a geometric series a + ar + ar^2 + ... + ar^(n-1) is given by (a(1 - r^n)) / (1 - r). Substituting a = 3n and r = 1/2, we find the closed form of the series:
T(n) = (3n (1 - (1/2)^log2(n))) / (1 - 1/2) = 6n - 3
By this calculation, the precise function of n in closed form for the given recurrence relation is T(n) = 6n - 3.