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 \end{eqnarray*} \)

Comments

Find and fix any errors in the above, then return to the hints page for help with the rest of the calculation.