Hi all, thanks in advance for any help.
This is the question:
Solve the following recurrence relation by forward substitution and then verify the result by mathematical induction:
T(n) = 2T(n/7) for n > 1, n is a power of 7
T(1) = 1
My answer:
T(7) = 2T(7/7) = 2T(1) = 2
T(14) = 2T(14/7) = 2T(2) = 2^2
T(21) = 2T(21/7) = 2T(3) = 2^3
T(28) = 2T(28/7) = 2T(4) = 2^4
(I'm not sure if going up in 7's is correct)
Solution for recurrence relation: T(n) = 2^log n
T(1) = 2^log 1 = 2^0 = 1
T(2n) = 2T(2n/2) = 2T(n) = 2^1 x 2^log n
= 2^ log 2n
Check answer for T(14) = 2^2
2^log n = 2^log 14 = 2^7^2 (two to the power of 7 squared) = 2^7log2 = 2^2
I managed to do this because of an example given, I don't know if its correct. I would appreciate if somebody could check/walk through each stage. Thanks again.
