Unrolling Problem 1

Here is the recursive definition, for reference

\(T(1) = 5 \)

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

Hints for getting started

If you are stuck getting started, remember the basic steps of the method:

  1. Substitute the recursive equation for T into itself twice.
  2. Guess the pattern for what you'll get after k substitutions.
  3. Solve for when the input to T will equal the base case input.
  4. Substitute these base-case values into the equation.
  5. Clean up the result.

Step 1

To substitute the equation into itself, you'll need to work out the value for T(n/2). Write out what T(n/2) is before doing the substitution:

\( T(n/2) = 3 T(n/4) + 7\)

Your next substitution will be for T(n/4). Write out what that is. Then substitute these two equations into the original one.

You should have this.

Step 2

That's enough substitutions to satsify the instructions for the problem. However, if you don't see the pattern emerging, you might try one more substitution. Also try cleaning up your equation by (for example) collapsing several multiplications by 3 into a power of three. Write all powers in exponential notation to make patterns more obvious, e.g. \(3^3\) rather than 27.

If your equation is written out using a list of terms with \(\dots\), convert this to summation notation.

You should have something like this.

Steps 3 and 4

Now, you need to eliminate k from the equation.

For step 3, you need to figure out what value of k will make the input to T equal the base-case input. In the base case of the original definition of T, the input is 1. What's the input to T in your partial solution? Set this equal to 1 and solve the resulting equation for k.

Finally, substitute your value for k into the equation. You should have an equation that shows how T(n) is related to T(1). What is the value of T(1)? It's a constant, right? Look back at the definition of T and substitute this base-case value into your equation. You should now have an equation expressing T(n) just in terms of n. No recursive calls to T, no use of the temporary variable k.

When you've got the first four steps worked out, check your partial solution.

Step 5

Now, you need to clean up your solution. There's two steps that may not be obvious:

  1. Simplify cases where you have a log in an exponent.
  2. Replace the summation with its closed form.

To deal with logs in exponents, first remember that \(k^{\log_k n} = n\). That's what log does: it undoes the effect of exponentiation. This simple version works only when the base of the exponent matches the base of the log. If they don't match, you'll need to look up the formula for changing the base of a log.

For the summation, you may need to use a table of common summation closed forms. Try the web, e.g. wikipedia. The one you're looking for is an extremely common, frequently used summation. You might have seen it, or something very similar, in Calculus classes.

Check your final answer against the full solution.