Finding Fibonacci – Exponential vs. Linear

2nd Friday Fun Session – 13th Jan 2017

What is Fibonacci number?

0, 1, 2, 3, 5, 8 . . . is Fibonacci series where 1st number is 0, 2nd number 1, 3rd number 2 and so on, each number being the sum of its two predecessors.

What are we talking about here?

We will see that nth Fibonacci number can be found using both recursive and iterative methods. Recursive one will be prohibitively expensive while iterative one will be much more efficient.

Recursive solution

We can use the following recursive function to get nth Fibonacci number.

int FibonacciExponential(int n, int &opCounter)
{
  opCounter++;

  if(n == 0 || n == 1)
    return n;

  return FibonacciExponential(n-1, opCounter) + 
         FibonacciExponential(n-2, opCounter);
}

We have passed an extra parameter to count the number of times the recursive function gets called. For example, for n = 4, we see we have the following calls, each node showing the value of n, with which the function is called. Many a times, for a certain value of n, the function is called numerous times.

Fibonacci Call Tree

We see, if we increase n by one, the tree also expands by one more level. For n = 4 we end up with 24 (2 raised to the 4th power) calls. It will be few less as the right sub-tree is one level less than the left, but they are negligible. When the input number n (input size) goes as an exponent, we call the complexity – exponential. Especially, when we talk about Big O notation, we express it using the upper asymptotic bound. The complexity here is O(2n).

The value 2n when n = 100, is 2100 = 1267650600228229401496703205376. What if each operation takes a millisecond? The execution time would be trillions of years ~ just for n = 100!

Iterative solution

We could as well run a simple loop by retaining the previous two values and add them to find the present Fibonacci number. For n = 100, we just needed to loop maximum 100 times, requiring 100 operations. That means, we could call the complexity linear and in terms of big O notation it would be O(n).

The below function finds nth Fibonacci number iteratively, in linear time.

int FibonacciLinear(int n, int &opCounter)
{
  opCounter++;
 
  if(n == 0 || n == 1)
    return n;

  int result = 0;
  int previousPrevious = 0;
  int immediatePrevious = 1; 

  for(int i=2; i<=n; i++)
  {
    opCounter++;
 
    result = immediatePrevious + previousPrevious;

    previousPrevious = immediatePrevious;
    immediatePrevious = result;
  }
 
  return result;;
}

Considering each operation taking 1 millisecond, we are talking about 100 milliseconds for linear algorithm vs. trillions of years for exponential algorithm.

GitHub: Fibonacci Code

Index

Author: Gopal Das

I am working as a Principal Consultant at JLT Interactive Pte Ltd, Singapore. I have a BS in Computer Science & Engineering from Khulna University and ME in Internet Science & Engineering from Indian Institute of Science (IISc). I have a few publications on Query Optimization in RDBMS in ACM SIGMOD, IEEE ICDE etc. I was a founding team member and VP Engineering of iTwin, a spinoff from A*STAR. I am working as a software engineer for 14 years. I am interested in Algorithms, Database, Security, Machine Learning, and Blockchain among others. I am a father of two children and live in Singapore. www.linkedin.com/in/dasgopal https://github.com/gopalcdas

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s