Recurrence relation solution
- by Travis
I'm revising past midterms for a final exam this week and am trying to make sense of a solution my professor posted for one of past exams. (You can see the original pdf here, question #6).
I'm given the original recurrence relation T(m)=3T(n/2) + n and am told T(1) = 1.
I'm pretty sure the solution I've been given is wrong in a few places. The solution is as follows:
Let n=2^m
T(2^m) = 3T(2^(m-1)) + 2^m
3T(2^(m-1)) = 3^2*T(2^(m-2)) + 2^(m-1)*3
...
3^(m-1)T(2) = T(1) + 2*3^(m-1)
I'm pretty sure this last line is incorrect and they forgot to multiply T(1) by 3^m.
He then (tries to) sum the expressions:
T(2^m) = 1 + (2^m + 2^(m-1)*3 + ... + 2*3(m-1))
= 1 + 2^m(1 + (3/2)^1 + (3/2)^2 + ... + (3/2)^(m-1))
= 1 + 2^m((3/2)^m-1)*(1/2)
= 1 + 3^m - 2^(m-1)
= 1 + n^log 3 - n/2
Thus the algorithm is big Theta of (n^log 3).
I'm pretty sure that he also got the summation wrong here. By my calculations this should be as follows:
T(2^m) = 2^m + 3 * 2^(m-1) + 3^2 * 2^(m-2) + ... + 3^m
(3^m because 3^m*T(1) = 3^m should be added, not 1)
= 2^m * ((3/2)^1 + (3/2)^2 + ... + (3/2)^m)
= 2^m * sum of (3/2)^i from i=0 to m
= 2^m * ((3/2)^(m+1) - 1)/(3/2 - 1)
= 2^m * ((3/2)^(m+1) - 1)/(1/2)
= 2^(m+1) * 3^(m+1)/2^(m+1) - 2^(m+1)
= 3^(m+1) - 2 * 2^m
Replacing n = 2^m, and from that m = log n
T(n) = 3*3^(log n) - 2*n
n is O(3^log n), thus the runtime is big Theta of (3^log n)
Does this seem right? Thanks for your help!
