Find Nth term of any Linear Recurrence Relation in O(logN) complexity.

general
, ,
1

Find Nth term of any Linear Recurrence Relation( like Fibonacci sequence ) in O(logN)

2

Is matrix multiplication O(1) ?

3

yes @shashwat001
O(1) means constant time… each matrix multiplication (given that both matrix have same dimension) will take constant time (a fixed amount of computations which won’t depend on any other factor like n,k ) …

4

matrix multiplication will be O(k^3). (Its better than using the divide and conquer approach which has high constant factor).

1 Like
5

agree… where k is dimension of matrix right ?

1 Like