The solution to the recurrence equation
2002
The solution to the recurrence equation
- A.
2k
- B.
(3k+1-1)/2
- C.
3 log2 k
- D.
2 log3 k
Attempted by 26 students.
Show answer & explanation
Correct answer: B
Let S(k) = T(2^k). The recurrence transforms to S(k) = 3S(k-1) + 1 with base case S(0)=1.
Solving this linear recurrence gives the general form S(k) = c * 3^k - 1/2.
Applying the base case S(0)=1 determines c = 3/2, resulting in the solution (3^(k+1)-1)/2.
A video solution is available for this question — log in and enroll to watch it.