9

Finding the nth term in Fibonacci series f(n) = f(n-1) + f(n-2) can be solved in O(n) time by memoization.

A more efficient way would be to find the nth power of matrix [ [1,1] , [1,0] ] using divide and conquer to solve the Fibonacci in log n time.

Is there similar approach which can be followed for f(n) = f(n-1) + f(n-x) + f(n-x+1) [ x is some constant ].

Just be storing previous x elements, this can solved in O(n) time.

Is there a better way to solve this recursion.

elricL
  • 1,188
  • 3
  • 11
  • 20
  • 4
    That's a nice question, but you'll probably get better answers at math.stackexchange.com – phimuemue Oct 07 '11 at 10:49
  • 2
    ...or http://cstheory.stackexchange.com/ – NPE Oct 07 '11 at 10:51
  • Maybe you could have a look at http://www.cs.uiuc.edu/~jeffe/teaching/373/notes/recurrences.pdf and try to adapt the presented tools to calculate a specific solution for your problem. – phimuemue Oct 07 '11 at 11:25
  • Same way, but the size of the matrix will be x by x. Weather or not this is efficient will depend on the relative sizes of x and n. – phkahler Oct 07 '11 at 11:28

2 Answers2

8

As you are already suspecting, this will work very similar. Use the n-th power of the x * x matrix

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

This is easy to understand if you multiply this matrix with the 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 be done in O(log(n)) time (when x is considered to be constant).

For the Fibonacci recurrence, there is also a closed formula solution, see here http://en.wikipedia.org/wiki/Fibonacci_number, look for Binet's or Moivre's formula.

Doc Brown
  • 19,739
  • 7
  • 52
  • 88
  • 1
    Binet's formula isn't O(1) because it contains nth powers that need to be evaluated to a high enough precision. In practice it is slower than the binary exponentiation of the matrix. – Sven Marnach Oct 07 '11 at 11:34
  • Note that there is also a closed form solution for this case. Simply diagonlise the recursion matrix. Taking the nth power will decouple into `x` scalars being raised to the nth power, and you only need to transform back to the original basis once. (Well, I suspect this explanation is a bit terse for this forum, but anyway...) – Sven Marnach Oct 07 '11 at 11:44
  • I thought of this, but is there a more efficient way to do it? This would take O((x^3)*logn). – elricL Oct 07 '11 at 11:46
  • 3
    @elricL: Careful with these complexities. Since the involved numbers get big, we can't assume that – say – an addition is O(1). Even computing something as simple as 3^n is O(n log(n)). As to your original question: Binary exponentiation of the recursion matrix (without diagonalising) is probably your best bet since it will have the same complexity as the solution *with* diagonalising, but the former can be done in integer arithmetic. – Sven Marnach Oct 07 '11 at 11:55
  • @elricL: You can get do the matrix multiplication in O(x²) with a bit of insight (compute one row in O(x²), then compute the other rows each in O(x)) – Nabb Oct 07 '11 at 17:06
2

You may want to look into Tribonacci numbers (and other generalizations of Fiboniacci numbers.) They have been studied quite extensively. See e.g. Generalizations of Fibonacci numbers

user980473
  • 31
  • 4