# Unrolling Problem 1

Here is the recursive definition, for reference

$$T(1) = 5$$

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

### 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*}$$

The input to T will hit the base case input value when $$n/2^k = 1$$. That is, we need to have $$n = 2^k$$. So $$k = \log_2 n$$.

Substituting in the base case value for k and the fact that T(1)=5, we get:

$$\begin{eqnarray*} T(n) &=& 3^{\log_2 n} \cdot T(1) + 7 \sum_{i=0}^{\log_2 n-1}3^i = 5\cdot 3^{\log_2 n} + 7 \sum_{i=0}^{\log_2 n-1}3^i \\ \end{eqnarray*}$$

Notice that $$3^{\log_2 n}= 3^{\log_3 n \cdot \log_2 3}= n^{\log_2 3}$$.

From any standard summation table, we find that $$\displaystyle\sum_{i=0}^{p}r^i = \frac{r^{p+1} -1}{r-1}$$

So $$\displaystyle\sum_{i=0}^{\log_2 n-1}3^i = \frac{3^{\log_2 n} -1}{3-1} = \frac{n^{\log_2 3} -1}{2}$$

So $$\displaystyle T(n) = 5\cdot 3^{\log_2 n} + 7 \sum_{i=0}^{\log_2 n-1}3^i = 5\cdot n^{\log_2{3}} + 7 \frac{n^{\log_2{3}}- 1}{2} = \frac{17n^{\log_2 3} -7}{2}$$