Computational complexity of Fibonacci Sequence

Question

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 Fibonacci int n        if  n  lt   1          return n      else         return Fibonacci n - 1    Fibonacci n - 2       What is the computational complexity of the Fibonacci sequence and how is it calculated

User · Accepted Answer

You model the time function to calculate Fib(n) as sum of time to calculate Fib(n-1) plus the time to calculate Fib(n-2) plus the time to add them together (O(1)). This is assuming that repeated evaluations of the same Fib(n) take the same time - i.e. no memoization is use.

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

You solve this recurrence relation (using generating functions, for instance) and you'll end up with the answer.

Alternatively, you can draw the recursion tree, which will have depth n and intuitively figure out that this function is asymptotically O(2ⁿ). You can then prove your conjecture by induction.

Base: n = 1 is obvious

Assume T(n-1) = O(2^n-1), therefore

T(n) = T(n-1) + T(n-2) + O(1) which is equal to

T(n) = O(2^n-1) + O(2^n-2) + O(1) = O(2ⁿ)

However, as noted in a comment, this is not the tight bound. An interesting fact about this function is that the T(n) is asymptotically the same as the value of Fib(n) since both are defined as

f(n) = f(n-1) + f(n-2).

The leaves of the recursion tree will always return 1. The value of Fib(n) is sum of all values returned by the leaves in the recursion tree which is equal to the count of leaves. Since each leaf will take O(1) to compute, T(n) is equal to Fib(n) x O(1). Consequently, the tight bound for this function is the Fibonacci sequence itself (~?(1.6ⁿ)). You can find out this tight bound by using generating functions as I'd mentioned above.

User · Answer

You can expand it and have a visulization         T n    T n-1    T n-2   lt       T n-1    T n-1           2 T n-1            2 2 T n-2         2 2 2 T n-3                   2 i T n-i                   gt  O 2 n

User · Answer

I agree with pgaur and rickerbh  recursive-fibonacci s complexity is O 2 n    I came to the same conclusion by a rather simplistic but I believe still valid reasoning   First  it s all about figuring out how many times recursive fibonacci function   F   from now on   gets called when calculating the Nth fibonacci number  If it gets called once per number in the sequence 0 to n  then we have O n   if it gets called n times for each number  then we get O n n   or O n 2   and so on   So  when F   is called for a number n  the number of times F   is called for a given number between 0 and n-1 grows as we approach 0   As a first impression  it seems to me that if we put it in a visual way  drawing a unit per time F   is called for a given number  wet get a sort of pyramid shape  that is  if we center units horizontally   Something like this   n                n-1               n-2                      2                       1                          0                                  Now  the question is  how fast is the base of this pyramid enlarging as n grows   Let s take a real case  for instance F 6   F 6                      lt -- only once F 5                      lt -- only once too F 4                      F 3                      F 2                        F 1                                       lt -- 16 F 0                                        lt -- 32   We see F 0  gets called 32 times  which is 2 5  which for this sample case is 2  n-1    Now  we want to know how many times F x  gets called at all  and we can see the number of times F 0  is called is only a part of that    If we mentally move all the   s from F 6  to F 2  lines into F 1  line  we see that F 1  and F 0  lines are now equal in length  Which means  total times F   gets called when n 6 is 2x32 64 2 6   Now  in terms of complexity   O  F 6      O 2 6  O  F n      O 2 n

User · Answer

The naive recursion version of Fibonacci is exponential by design due to repetition in the computation   At the root you are computing   F n  depends on F n-1  and F n-2   F n-1  depends on F n-2  again and F n-3   F n-2  depends on F n-3  again and F n-4   then you are having at each level 2 recursive calls that are wasting a lot of data in the calculation  the time function will look like this   T n    T n-1    T n-2    C  with C constant  T n-1    T n-2    T n-3    T n-2  then  T n    2 T n-2        T n    2  n 2    T 1    O 2  n 2    This is just a lower bound that for the purpose of your analysis should be enough but the real time function is a factor of a constant by the same Fibonacci formula and the closed form is known to be exponential of the golden ratio   In addition  you can find optimized versions of Fibonacci using dynamic programming like this   static int fib int n           memory        int f     new int n 1       int i          Init        f 0    0      f 1    1          Fill        for  i   2  i  lt   n  i                  f i    f i-1    f i-2              return f n       That is optimized and do only n steps but is also exponential   Cost functions are defined from Input size to the number of steps to solve the problem  When you see the dynamic version of Fibonacci  n steps to compute the table  or the easiest algorithm to know if a number is prime  sqrt n  to analyze the valid divisors of the number   you may think that these algorithms are O n  or O sqrt n   but this is simply not true for the following reason  The input to your algorithm is a number  n  using the binary notation the input size for an integer n is log2 n  then doing a variable change of  m   log2 n     your real input size   let find out the number of steps as a function of the input size  m   log2 n  2 m   2 log2 n    n   then the cost of your algorithm as a function of the input size is   T m    n steps   2 m steps   and this is why the cost is an exponential

User · Answer

Just ask yourself how many statements need to execute for F n  to complete   For F 1   the answer is 1  the first part of the conditional    For F n   the answer is F n-1    F n-2    So what function satisfies these rules   Try an  a   1    an    a n-1    a n-2   Divide through by a n-2    a2    a   1  Solve for a and you get  1 sqrt 5   2   1 6180339887  otherwise known as the golden ratio   So it takes exponential time

User · Answer

The proof answers are good  but I always have to do a few iterations by hand to really convince myself   So I drew out a small calling tree on my whiteboard  and started counting the nodes   I split my counts out into total nodes  leaf nodes  and interior nodes   Here s what I got   IN   OUT   TOT   LEAF   INT  1     1     1     1      0  2     1     1     1      0  3     2     3     2      1  4     3     5     3      2  5     5     9     5      4  6     8    15     8      7  7    13    25    13     12  8    21    41    21     20  9    34    67    34     33 10    55   109    55     54   What immediately leaps out is that the number of leaf nodes is fib n    What took a few more iterations to notice is that the number of interior nodes is fib n  - 1   Therefore the total number of nodes is 2   fib n  - 1   Since you drop the coefficients when classifying computational complexity  the final answer is   fib n

User · Answer

There s a very nice discussion of this specific problem over at MIT   On page 5  they make the point that  if you assume that an addition takes one computational unit  the time required to compute Fib N  is very closely related to the result of Fib N    As a result  you can skip directly to the very close approximation of the Fibonacci series   Fib N     1 sqrt 5     1 618  N 1   approximately    and say  therefore  that the worst case performance of the naive algorithm is   O  1 sqrt 5     1 618  N 1     O 1 618  N 1     PS  There is a discussion of the closed form expression of the Nth Fibonacci number over at Wikipedia if you d like more information

User · Answer

It is bounded on the lower end by 2  n 2  and on the upper end by 2 n  as noted in other comments    And an interesting fact of that recursive implementation is that it has a tight asymptotic bound of Fib n  itself   These facts can be summarized   T n    O 2  n 2     lower bound  T n    O 2 n     upper bound  T n    T Fib n    tight bound    The tight bound can be reduced further using its closed form if you like

User · Answer

Recursive algorithm s time complexity can be better estimated by drawing recursion tree  In this case the recurrence relation for drawing recursion tree would be T n  T n-1  T n-2  O 1   note that each step takes O 1  meaning constant time since it does only one comparison to check value of n in if block Recursion tree would look like            n     n-1        n-2   n-2  n-3   n-3  n-4     so on   Here lets say each level of above tree is denoted by i hence   i 0                        n 1             n-1                   n-2  2         n-2      n-3        n-3       n-4  3    n-3  n-4   n-4  n-5   n-4  n-5   n-5  n-6    lets say at particular value of i  the tree ends  that case would be when n-i 1  hence i n-1  meaning that the height of the tree is n-1  Now lets see how much work is done for each of n layers in tree Note that each step takes O 1  time as stated in recurrence relation   2 0 1                        n 2 1 2             n-1                   n-2  2 2 4         n-2      n-3        n-3       n-4  2 3 8    n-3  n-4   n-4  n-5   n-4  n-5   n-5  n-6       so on 2 i for ith level   since i n-1 is height of the tree work done at each level will be  i work 1 2 1 2 2 2 3 2 3  so on   Hence total work done will sum of work done at each level  hence it will be 2 0 2 1 2 2 2 3    2  n-1  since i n-1  By geometric series this sum is 2 n  Hence total time complexity here is O 2 n

User · Answer

The proof answers are good  but I always have to do a few iterations by hand to really convince myself   So I drew out a small calling tree on my whiteboard  and started counting the nodes   I split my counts out into total nodes  leaf nodes  and interior nodes   Here s what I got   IN   OUT   TOT   LEAF   INT  1     1     1     1      0  2     1     1     1      0  3     2     3     2      1  4     3     5     3      2  5     5     9     5      4  6     8    15     8      7  7    13    25    13     12  8    21    41    21     20  9    34    67    34     33 10    55   109    55     54   What immediately leaps out is that the number of leaf nodes is fib n    What took a few more iterations to notice is that the number of interior nodes is fib n  - 1   Therefore the total number of nodes is 2   fib n  - 1   Since you drop the coefficients when classifying computational complexity  the final answer is   fib n

User · Answer

It is simple to calculate by diagramming function calls   Simply add the function calls for each value of n and look at how the number grows   The Big O is O Z n  where Z is the golden ratio or about 1 62   Both the Leonardo numbers and the Fibonacci numbers approach this ratio as we increase n    Unlike other Big O questions there is no variability in the input and both the algorithm and implementation of the algorithm are clearly defined   There is no need for a bunch of complex math   Simply diagram out the function calls below and fit a function to the numbers   Or if you are familiar with the golden ratio you will recognize it as such   This answer is more correct than the accepted answer which claims that it will approach f n    2 n   It never will   It will approach f n    golden ratio n   2  2 - gt  1  0   4  3 - gt  2  1   2 - gt  1  0   8  4 - gt  3  2   3 - gt  2  1   2 - gt  1  0               2 - gt  1  0    14  5 - gt  4  3   4 - gt  3  2   3 - gt  2  1   2 - gt  1  0               2 - gt  1  0                3 - gt  2  1   2 - gt  1  0   22  6 - gt  5  4               5 - gt  4  3   4 - gt  3  2   3 - gt  2  1   2 - gt  1  0                           2 - gt  1  0                            3 - gt  2  1   2 - gt  1  0                4 - gt  3  2   3 - gt  2  1   2 - gt  1  0                           2 - gt  1  0

User · Answer

You can expand it and have a visulization         T n    T n-1    T n-2   lt       T n-1    T n-1           2 T n-1            2 2 T n-2         2 2 2 T n-3                   2 i T n-i                   gt  O 2 n

User · Answer

It is bounded on the lower end by 2  n 2  and on the upper end by 2 n  as noted in other comments    And an interesting fact of that recursive implementation is that it has a tight asymptotic bound of Fib n  itself   These facts can be summarized   T n    O 2  n 2     lower bound  T n    O 2 n     upper bound  T n    T Fib n    tight bound    The tight bound can be reduced further using its closed form if you like

User · Answer

There s a very nice discussion of this specific problem over at MIT   On page 5  they make the point that  if you assume that an addition takes one computational unit  the time required to compute Fib N  is very closely related to the result of Fib N    As a result  you can skip directly to the very close approximation of the Fibonacci series   Fib N     1 sqrt 5     1 618  N 1   approximately    and say  therefore  that the worst case performance of the naive algorithm is   O  1 sqrt 5     1 618  N 1     O 1 618  N 1     PS  There is a discussion of the closed form expression of the Nth Fibonacci number over at Wikipedia if you d like more information

User · Answer

Well  according to me to it is O 2 n  as in this function only recursion is taking the considerable time  divide and conquer   We see that  the above function will continue in a tree until the leaves are approaches when we reach to the level F n- n-1   i e  F 1   So  here when we jot down the time complexity encountered at each depth of tree  the summation series is   1 2 4         n-1    1  2 n -1   2-1   2 n -1   that is order of 2 n   O 2 n

User · Answer

It is simple to calculate by diagramming function calls   Simply add the function calls for each value of n and look at how the number grows   The Big O is O Z n  where Z is the golden ratio or about 1 62   Both the Leonardo numbers and the Fibonacci numbers approach this ratio as we increase n    Unlike other Big O questions there is no variability in the input and both the algorithm and implementation of the algorithm are clearly defined   There is no need for a bunch of complex math   Simply diagram out the function calls below and fit a function to the numbers   Or if you are familiar with the golden ratio you will recognize it as such   This answer is more correct than the accepted answer which claims that it will approach f n    2 n   It never will   It will approach f n    golden ratio n   2  2 - gt  1  0   4  3 - gt  2  1   2 - gt  1  0   8  4 - gt  3  2   3 - gt  2  1   2 - gt  1  0               2 - gt  1  0    14  5 - gt  4  3   4 - gt  3  2   3 - gt  2  1   2 - gt  1  0               2 - gt  1  0                3 - gt  2  1   2 - gt  1  0   22  6 - gt  5  4               5 - gt  4  3   4 - gt  3  2   3 - gt  2  1   2 - gt  1  0                           2 - gt  1  0                            3 - gt  2  1   2 - gt  1  0                4 - gt  3  2   3 - gt  2  1   2 - gt  1  0                           2 - gt  1  0

User · Answer

There s a very nice discussion of this specific problem over at MIT   On page 5  they make the point that  if you assume that an addition takes one computational unit  the time required to compute Fib N  is very closely related to the result of Fib N    As a result  you can skip directly to the very close approximation of the Fibonacci series   Fib N     1 sqrt 5     1 618  N 1   approximately    and say  therefore  that the worst case performance of the naive algorithm is   O  1 sqrt 5     1 618  N 1     O 1 618  N 1     PS  There is a discussion of the closed form expression of the Nth Fibonacci number over at Wikipedia if you d like more information

User · Answer

Well  according to me to it is O 2 n  as in this function only recursion is taking the considerable time  divide and conquer   We see that  the above function will continue in a tree until the leaves are approaches when we reach to the level F n- n-1   i e  F 1   So  here when we jot down the time complexity encountered at each depth of tree  the summation series is   1 2 4         n-1    1  2 n -1   2-1   2 n -1   that is order of 2 n   O 2 n

User · Answer

There s a very nice discussion of this specific problem over at MIT   On page 5  they make the point that  if you assume that an addition takes one computational unit  the time required to compute Fib N  is very closely related to the result of Fib N    As a result  you can skip directly to the very close approximation of the Fibonacci series   Fib N     1 sqrt 5     1 618  N 1   approximately    and say  therefore  that the worst case performance of the naive algorithm is   O  1 sqrt 5     1 618  N 1     O 1 618  N 1     PS  There is a discussion of the closed form expression of the Nth Fibonacci number over at Wikipedia if you d like more information

User · Answer

Just ask yourself how many statements need to execute for F n  to complete   For F 1   the answer is 1  the first part of the conditional    For F n   the answer is F n-1    F n-2    So what function satisfies these rules   Try an  a   1    an    a n-1    a n-2   Divide through by a n-2    a2    a   1  Solve for a and you get  1 sqrt 5   2   1 6180339887  otherwise known as the golden ratio   So it takes exponential time

User · Answer

Just ask yourself how many statements need to execute for F n  to complete   For F 1   the answer is 1  the first part of the conditional    For F n   the answer is F n-1    F n-2    So what function satisfies these rules   Try an  a   1    an    a n-1    a n-2   Divide through by a n-2    a2    a   1  Solve for a and you get  1 sqrt 5   2   1 6180339887  otherwise known as the golden ratio   So it takes exponential time

User · Answer

Just ask yourself how many statements need to execute for F n  to complete   For F 1   the answer is 1  the first part of the conditional    For F n   the answer is F n-1    F n-2    So what function satisfies these rules   Try an  a   1    an    a n-1    a n-2   Divide through by a n-2    a2    a   1  Solve for a and you get  1 sqrt 5   2   1 6180339887  otherwise known as the golden ratio   So it takes exponential time

User · Answer

The naive recursion version of Fibonacci is exponential by design due to repetition in the computation   At the root you are computing   F n  depends on F n-1  and F n-2   F n-1  depends on F n-2  again and F n-3   F n-2  depends on F n-3  again and F n-4   then you are having at each level 2 recursive calls that are wasting a lot of data in the calculation  the time function will look like this   T n    T n-1    T n-2    C  with C constant  T n-1    T n-2    T n-3    T n-2  then  T n    2 T n-2        T n    2  n 2    T 1    O 2  n 2    This is just a lower bound that for the purpose of your analysis should be enough but the real time function is a factor of a constant by the same Fibonacci formula and the closed form is known to be exponential of the golden ratio   In addition  you can find optimized versions of Fibonacci using dynamic programming like this   static int fib int n           memory        int f     new int n 1       int i          Init        f 0    0      f 1    1          Fill        for  i   2  i  lt   n  i                  f i    f i-1    f i-2              return f n       That is optimized and do only n steps but is also exponential   Cost functions are defined from Input size to the number of steps to solve the problem  When you see the dynamic version of Fibonacci  n steps to compute the table  or the easiest algorithm to know if a number is prime  sqrt n  to analyze the valid divisors of the number   you may think that these algorithms are O n  or O sqrt n   but this is simply not true for the following reason  The input to your algorithm is a number  n  using the binary notation the input size for an integer n is log2 n  then doing a variable change of  m   log2 n     your real input size   let find out the number of steps as a function of the input size  m   log2 n  2 m   2 log2 n    n   then the cost of your algorithm as a function of the input size is   T m    n steps   2 m steps   and this is why the cost is an exponential

User · Answer

I agree with pgaur and rickerbh  recursive-fibonacci s complexity is O 2 n    I came to the same conclusion by a rather simplistic but I believe still valid reasoning   First  it s all about figuring out how many times recursive fibonacci function   F   from now on   gets called when calculating the Nth fibonacci number  If it gets called once per number in the sequence 0 to n  then we have O n   if it gets called n times for each number  then we get O n n   or O n 2   and so on   So  when F   is called for a number n  the number of times F   is called for a given number between 0 and n-1 grows as we approach 0   As a first impression  it seems to me that if we put it in a visual way  drawing a unit per time F   is called for a given number  wet get a sort of pyramid shape  that is  if we center units horizontally   Something like this   n                n-1               n-2                      2                       1                          0                                  Now  the question is  how fast is the base of this pyramid enlarging as n grows   Let s take a real case  for instance F 6   F 6                      lt -- only once F 5                      lt -- only once too F 4                      F 3                      F 2                        F 1                                       lt -- 16 F 0                                        lt -- 32   We see F 0  gets called 32 times  which is 2 5  which for this sample case is 2  n-1    Now  we want to know how many times F x  gets called at all  and we can see the number of times F 0  is called is only a part of that    If we mentally move all the   s from F 6  to F 2  lines into F 1  line  we see that F 1  and F 0  lines are now equal in length  Which means  total times F   gets called when n 6 is 2x32 64 2 6   Now  in terms of complexity   O  F 6      O 2 6  O  F n      O 2 n

User · Answer

It is bounded on the lower end by 2  n 2  and on the upper end by 2 n  as noted in other comments    And an interesting fact of that recursive implementation is that it has a tight asymptotic bound of Fib n  itself   These facts can be summarized   T n    O 2  n 2     lower bound  T n    O 2 n     upper bound  T n    T Fib n    tight bound    The tight bound can be reduced further using its closed form if you like

User · Answer

It is bounded on the lower end by 2  n 2  and on the upper end by 2 n  as noted in other comments    And an interesting fact of that recursive implementation is that it has a tight asymptotic bound of Fib n  itself   These facts can be summarized   T n    O 2  n 2     lower bound  T n    O 2 n     upper bound  T n    T Fib n    tight bound    The tight bound can be reduced further using its closed form if you like

User · Answer

Recursive algorithm s time complexity can be better estimated by drawing recursion tree  In this case the recurrence relation for drawing recursion tree would be T n  T n-1  T n-2  O 1   note that each step takes O 1  meaning constant time since it does only one comparison to check value of n in if block Recursion tree would look like            n     n-1        n-2   n-2  n-3   n-3  n-4     so on   Here lets say each level of above tree is denoted by i hence   i 0                        n 1             n-1                   n-2  2         n-2      n-3        n-3       n-4  3    n-3  n-4   n-4  n-5   n-4  n-5   n-5  n-6    lets say at particular value of i  the tree ends  that case would be when n-i 1  hence i n-1  meaning that the height of the tree is n-1  Now lets see how much work is done for each of n layers in tree Note that each step takes O 1  time as stated in recurrence relation   2 0 1                        n 2 1 2             n-1                   n-2  2 2 4         n-2      n-3        n-3       n-4  2 3 8    n-3  n-4   n-4  n-5   n-4  n-5   n-5  n-6       so on 2 i for ith level   since i n-1 is height of the tree work done at each level will be  i work 1 2 1 2 2 2 3 2 3  so on   Hence total work done will sum of work done at each level  hence it will be 2 0 2 1 2 2 2 3    2  n-1  since i n-1  By geometric series this sum is 2 n  Hence total time complexity here is O 2 n

[time-complexity] Computational complexity of Fibonacci Sequence

Examples related to time-complexity

Examples related to big-o

Examples related to complexity-theory

Examples related to fibonacci