Problem Code- CN05

Difficulty: Simple

Prerequisites:

Matrix Exponentiation

Explanation:

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

T(n-1)= 2*T(n-2)+ 3*T(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.