algorithm - Solving a Fibonacci like recurrence in log n time -

finding nth term in fibonacci series f(n) = f(n-1) + f(n-2) can solved in o(n) time memoization.

a more efficient way find nth power of matrix [ [1,1] , [1,0] ] using divide , conquer solve fibonacci in log n time.

is there similar approach can followed f(n) = f(n-1) + f(n-x) + f(n-x+1) [ x constant ].

just storing previous x elements, can solved in o(n) time.

is there better way solve recursion.

as suspecting, work similar. use n-th power of x * x matrix

|1 0 0 0  .... 1 1| |1  |  1 |    1 |      1 |        1 ................... ................... |          ... 1 0|

this easy understand if multiply matrix vector

f(n-1), f(n-2), ... , f(n-x+1), f(n-x)

which results in

f(n), f(n-1), ... , f(n-x+1)

matrix exponentiation can done in o(log(n)) time (when x considered constant).

for fibonacci recurrence, there closed formula solution, see here http://en.wikipedia.org/wiki/fibonacci_number, binet's or moivre's formula.

Support