An O(k2log(n/k)) Algorithm for Computing Generalized Order-k Fibonacci Numbers with Linear Space
M. C. Er · Journal of Information and Optimization Sciences · 1988
This paper presents an efficient algorithm for computing the nth term of the generalized order-k Fibonacci numbers using only O(k 2 log (n/k)) units of time and O(k) units of space. When n is less than a threshold, which is machine dependent, the time complexity of the algorithm is improved to O(kn). The time efficiency is achieved by using Er’s rule and a matrix representation of the generalized order-k Fibonacci numbers. On the other hand, the space efficiency is achieved by using an 1×k: matrix to represent an k×k matrix, as other rows of the square matrix can be derived from the one-row matrix. Overall, this algorithm is better than the previously known result.