Computational complexity of Fibonacci Sequence

Posted by Juliet on Stack Overflow See other posts from Stack Overflow or by Juliet
Published on 2008-12-11T20:20:25Z Indexed on 2010/04/28 20:37 UTC
Read the original article Hit count: 477

Filed under:

fibonacci

|

complexity

|

big-o

I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacci sequence:

int Fib(int n)
{
    if (n <= 1)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

What is the computational complexity of the Fibonnaci sequence and how is it calculated?

© Stack Overflow or respective owner

Related posts about fibonacci

What is going on with the "return fibonacci( number-1 ) + fibonacci( number-2 )"?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have problem understanding what the return fibonacci( number-1 ) + fibonacci( number-2 ) does in the following program: import sys def fibonacci( number ): if( number <= 2 ): return 1 else: return fibonacci( number-1 ) + fibonacci( number-2 ) The problem is that I… >>> More
Properties of bad fibonacci algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
I was looking at the canonical bad fibonacci algorithm the other day: public static int fib(int n) { // Base Case if (n < 2) return 1; else return fib(n-1) + fib(n-2); } I made the interesting observation. When you call fib(n), then for k between 1 and n fib(k)… >>> More
Code Chess: Fibonacci Sequence

as seen on Stack Overflow - Search for 'Stack Overflow'
Building upon the proven success of Code Golf, I would like to introduce Code Chess. Unlike Code Golf, which strives for concision, Code Chess will strive for cleverness. Can you create a clever or unexpected Fibonacci generator? Your code must print or return either the nth Fibonacci number or… >>> More
Test if a number is fibonacci

as seen on Stack Overflow - Search for 'Stack Overflow'
I know how to make the list of the Fibonacci numbers, but i don't know how can i test if a given number belongs to the fibonacci list - one way that comes in mind is generate the list of fib. numbers up to that number and see if it belongs to the array, but there's got to be another, simpler and faster… >>> More
Fibonacci numbers in F#

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
As you may have gathered from some of my previous posts, I've been spending some quality time at Project Euler. Normally I do my solutions in C#, but since I have also started learning F#, it only made sense to switch over to F# to get my math coding fix. This week's post is just a small snippet… >>> More

Related posts about complexity

Linear complexity and quadratic complexity

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm just not sure... If you have a code that can be executed in either of the following complexities: A sequence of O(n), like for example: two O(n) in sequence O(n²) The preferred version would be the one that can be executed in linear time. Would there be a time such that the sequence… >>> More
When should complexity be removed?

as seen on Programmers - Search for 'Programmers'
Prematurely introducing complexity by implementing design patterns before they are needed is not good practice. But if you follow all (or even most of) the SOLID principles and use common design patterns you will introduce some complexity as features and requirements are added or changed to keep… >>> More
Using Completed User Stories to Estimate Future User Stories

as seen on Programmers - Search for 'Programmers'
In Scrum/Agile, the complexity of a user story can be estimated in story points. After completing some user stories, a programmer or team of programmers can use those experiences to better estimate how much time it might take to complete a future user story. Is there a methodology for breaking down… >>> More
Finding complexity of a program as a service [on hold]

as seen on Programmers - Search for 'Programmers'
I would like to find the complexity of a specific code chunk written in Java. Is there a place/web site/service where I can find out the complexity of any arbitrary program. This program might include loops/recursion. Using theory we can compute complexity ourselves. But, just curious in finding… >>> More
Form, function and complexity in rule processing

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
Tim Bass posted on ‘Orwellian Event Processing’. I was involved in a heated exchange in the comments, and he has more recently published a post entitled ‘Disadvantages of Rule-Based Systems (Part 1)’. Whatever the rights and wrongs of our exchange, it clearly failed to generate any agreement or understanding… >>> More