The solution to the recurrence equation

2002

The solution to the recurrence equation

image.png

Answer: B. (3k+1-1)/2 — 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. A.

    2k

  2. B.

    (3k+1-1)/2

  3. C.

    3 log2 k

  4. D.

    2 log3 k

Attempted by 67 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.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…