CN05 - Editorial

Problem Code- CN05

Difficulty: Simple

Prerequisites:
Matrix Exponentiation

Explanation:

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

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

Therefore,

Let the matrix A = Row1:[2 3]
Row2: [1 0]

[T(n) ] = A^(n-1) * [ T(n-1) ]

[T(n-1)] [T(n-2) ]

So, use matrix exponentiation to find T(n) in O(lg N) time.