# 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}
\)

### Comments

If your final answer is incorrect, look for the location where your
calculations start to differ from the above. Make sure you understand
what went wrong. However, be aware that small errors are common with
this method. It's always wise to check your supposed closed form
against outputs of the original recursive definition and/or sketch
an inductive proof of correctness.

Notice that unrolling is not a proof. Although many parts of the calculation
would be ok in a formal proof, step 2 (guess the pattern) asks the reader
to simply have faith in your theory of what the pattern is.
Unrolling is a technique for finding out what the closed form is.
Proving the closed form correct requires induction.

In computer science, the default base for the log is 2. So, in some
contexts, you'll see this written simply as "log n".
We've marked the
base explicitly in this solution (even when it's 2) because some of the logs
have a different base. However, expect to see the base omitted when it's
(a) 2 for the whole problem or (b) the base doesn't matter e.g. in a
big-O algorithm analysis.