Unrolling Problem 1

Here is the recursive definition, for reference

\(T(1) = 5 \)

\( T(n) = 3 T(n/2) + 7\) for \(n \ge 2\)

Partial Solution

First, substitute the recursive part of the definition into itself and guess the pattern to get the result after k substitutions.

\( \begin{eqnarray*} T(n) &=& 3\cdot T(n/2) + 7 \\ &=& 3(3\cdot T(n/4) + 7) + 7 \\ &=& 3(3(3\cdot T(n/8) + 7) + 7) + 7 \\ &=& \ldots \\ &=& 3^k \cdot T(n/{2^k})+ 7 \sum_{i=0}^{k-1}3^i \\ \end{eqnarray*} \)