Question & Answer: Solve the recurrence relation : T(n) = T(n/2) + n3, T(1)=1……

Solve the recurrence relation : T(n) = T(n/2) + n³, T(1)=1.

1.Draw the first three levels of the recurrence tree.

2.Solve the recurrence to find a formula and find the Big(Oh) complexity.

Expert Answer

1. The following is the recurrence tree for the given recurrence relation.

2. Let us calculate the level at which the leaf of the tree lies.

At the leaf level we have

n = 2ⁱ where i is the leaf level

=> i = log₂(n)

Therefore there are log₂(n) + 1 levels in this tree starting from the 0th level to the log₂(n)-th level.

$T(n) = n^{3} +$ ${(frac{n}{2}})^{3}$ $+ ... + 1$ , which is in a geometric progression with common ratio $frac{1}{8}$

$implies T(n) = n^{3}(frac{1-{frac{1}{8}}^{log(n)+1}}{1-frac{1}{8}})$ since there are a total of ${log(n)+1}$ terms in the GP

$implies T(n) = (frac{8n^3-1}{7})$

Therefore by ignoring the constant terms and coefficients, the Big(oh) notation we have

$implies T(n) = O(n^3)$

Still stressed from student homework?

Get quality assistance from academic writers!

Order now