Playing with time complexity: Fibonacci Numbers

Famous Fibonacci sequence was defined by mathematician Leonardo Fibonacci during 15th century.



This can be defined mathematically as above.

Exponential Time algorithm

The above expression itself gives us the idea of evaluating Fibonacci values by using recursion. Well, it works but takes so much of memory that the calculation of larger Fibonacci values is merely impossible.

The pseudo code may be written as below

function fibonacci_number(n)
if n = 0: return 0
if n = 1: return 1
return fibonacci_number(n − 1) + fibonacci_number(n − 2)


The growth of above function is nearly in powers of two which leads to an exponential growth of time with increasing input n. Thus the above algorithm is identified as an exponential time algorithm.

Polynomial Time Algorithm

What is required is something simpler, faster and memory efficient. The same algorithm can be implemented by using the knowledge in polynomials. Whose pseudo code appears as bellow.


function fibonacci_number(n)
if n = 0 return 0
create an array f[0 . . . n]
f[0] = 0, f[1] = 1
for i = 2 . . . n:
        f[i] = f[i − 1] + f[i − 2]
return f[n]

Matrix based method



In this method the matrix relationship among Fibonacci numbers are used.


This is derived through simple arithmetic, which is clearly visible from first two steps and raised to a power by using the pattern derived.


Further this can be simplified by using matrices and eigen values, which will be discussed in a later log post.

A formula?

The above formula leaves us with a simple calculation. But in here the calculation of power, which involves multiplication is expensive for a computer. Thus the time complexity if O(M(n) log n) where M(n) is the time complexity in multiplying 2 n bit numbers.