Use iteration to find explicit formulas for the following re

Use iteration to find explicit formulas for the following recurrences. For each problem, show your work and draw a recursion tree. Assume T(1) = 1

1. T(n)=3T(n 2 ) + C, n = 2k

2. T(n)=3T(n 2 ) + n, n = 2k

Solution

1.

Given recurrence is

T(n) = 3T(n/2) +C                               n= 2^k

We, can proceed further by replacing T(n/2) with 3T(n/4) + C

T(n) = 9T(n/4) + 3C + C

Next replace T(n/4) by 3T(n/8) + C, to get

T(n) = 27T(n/8) + 9C +3C + C

In general we can write

T(n) = 3ⁱT(n/2ⁱ) + 3^i-1C + .........+ 3C + C

Given that n= 2^k now to reach to T(1), let i = k. Thus, we get

T(n) = 3^kT(1) + 3^k-1C + .........+ 3C + C

Using formula of geometric progression and putting T(1) = 1, we get

T(n) = 3^k + C [(3^k - 1)/(3-1)] = 3^k + [(3^k - 1) / 2] C

Now , k = log₂n, thus substituting in above equation we get

Therefore, T(n) = 3^log₂n + [(3^log₂n - 1) / 2] C = n^log₂3 + [(n^log₂3 - 1) / 2] C

2.

Given recurrence is

T(n) = 3T(n/2) + n                               n= 2^k

We, can proceed further by replacing T(n/2) with 3T(n/4) + n/2

T(n) = 9T(n/4) + 3n/2 + n

Next replace T(n/4) by 3T(n/8) + n/4, to get

T(n) = 27T(n/8) + 9n/4 +3n/2 + n

In general we can write

T(n) = 3ⁱT(n/2ⁱ) + 3^i-1n/2^i-1 + .........+ 3n/2 + n

Given that n= 2^k now to reach to T(1), let i = k. Thus, we get

T(n) = 3^kT(1) + 3^k-1n/2^k-1 + .........+ 3n/2 + n

Using formula of geometric progression and putting T(1) = 1, we get

T(n) = 3^k + n [((3/2)^k - 1)/(3/2-1)] = 3^k + 2n [(3/2)^k - 1 ]

Now , k = log₂n, thus substituting in above equation we get

Therefore, T(n) = 3^log₂n + 2n [(3/2)^log₂n - 1] = n^log₂3 + 2n [n^log₂3/2 - 1] = n^log₂3 + 2 [n^log₂3 - n]