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.