Search code examples
algorithmmaster-theorem

Solve the recurrences, T(n)=3T(n - 1)+3

Can someone please help me with this recurrences?

T(n)=3T(n - 1)+3

Explanation of steps would be greatly appreciated.

Solution

  • By educated guess, we can try a constant value, let t.

    t = 3t + 3

    is solved by t = -3/2.

    Now consider U(n) = T(n) + 3/2. The recurrence turns to

    U(n) - 3/2 = 3U(n-1) - 9/2 + 3

    or

    U(n) = 3U(n-1).

    Obviously,

    U(n) = U(0) 3^n.