Unwinding…

Finding the closed form

A problem that I found on the 2011 Fall Term Exam

Given the recurrence T(n) =  7T(n/3) + n ,  with the initial condition T(1) =  1. Assume that n is  a  power of the appropriate integer. Either by iterating the recurrence or by drawing a recursion tree with all details  as  presented in the notes, find  an exact closed-form solution.

We will solve by  iterating the recurrence(unwinding).  

The problem tells us to assume that n is a power of the appropriate integer. In this case it will be 3. The reason that we do this is to make sure that when n is divided by 3 to get T(n/3), we will know that the recursion will be of the right value and not a decimal rounded up or down which would make it harder for us to come to conclusions.

So assume that n = 3^a

So now we start unwinding…

T(n) =  7 T( n/3 ) + n                                                # i = 1

T(n) = 7 ( 7 T( n/9 ) + n/3 ) + n    

T(n) = 49 T( n/9 ) + 7n/3 + n                                    # i = 2

T(n) = 49 ( 7 T( n/27 ) + n/9) + 7n/3 + n 

T(n) = 343 T( n/27 ) + 49n/9 + 7n/3 + n                   # i = 3

T(n) = 343 ( 7 T( n/81 ) + n/27 ) + 49n/9  + 7n/3 + n

T(n) = 2611 T( n/81 ) +343n/27 + 49n/9 + 7n/3 + n  # i = 4

.

. The key point is to figure out what each recursion step would be in terms of i.

.

T(n) = 7ⁱ T( n/3ⁱ ) + 7^i-1n/3^i-1 + 7^i-2n/3^i-2 + … + 7⁰n/3⁰

T(n) = 7ⁱ T (n/3ⁱ ) + Σ(from k=0 to k = a – 1) (7/3)^kn

So, All the recursions would stop at T(1) since that was the only value that we were given that would give an answer without any recursion. In this case,  there will be no recursions when T(n/3ⁱ) = T(1)

     ð n/3ⁱ = 1

     ð n = 3ⁱ

     ð i = log₃ n

     ð i = log₃ 3^a

     ð i = a

Therefore, in the very last iteration, we could substitute i = a:

T(n) = 7^a T(1) +  n Σ(from k=0 to k = a – 1) (7/3)^kn

T(n) = 7^a + n (( 7/3 )^a – 1) / (( 7/3 ) – 1)

Therefore the closed form in terms of n would be: 

T(n) = 7^log(3) n + n (1 -(7/3)^log(3) n) / (1 -(7/3))