So I was trying to make a recursive fibonacci series algorithm on my own, just to give it a try. Then, I found out its time complexity to be of the order O(n) . But when I researched online, it says that the recursive fibonacci series algorithm has a time complexity of O(2^n) ??

This is my code in C:

#include <stdio.h>
void fibonacci(int n){
    int static a,b,c; //SO THAT VARIABLES CAN BE SHARED ACROSS FUNCTION CALLS
    if (n > 2)
    {
        fibonacci(n-1);
        c = a   b;
        printf("%d ",c);
        a = b;
        b = c;
    }
    if (n < 3)
    {
        a = 0;
        b = 1;
        if (n < 2)
        {
            printf("%d ",a);
        }
        else
        {
            printf("%d %d ",a,b);
        }   
    }
}

int main()
{
    fibonacci(10); //FINDING THE FIRST 10 FIBONACCI NUMBERS
    return 0;
}

I realize that the usage of static variables has changed something, but im not very clear what exactly and would love a more clear explanation!

I've been generally having trouble finding time complexities of recursive algorithms so im sorry if this is something very trivial. Thanks

CodePudding user response：

Your code really has linear complexity. It is because of memoization. Memoization is a technique used in dynammic programming.

Computation of the next Fibonacci number requires two preceding numbers, which leads to quadratic algorithm in it's naive implementation. With this approach, you repeatedly calculate numbers that you've already calculated.

However if you first calculate both predecessors and then just shift values, you end up with linear complexity. You made this possible with static variables that hold their values between calls.

Here, you can try to run both of the mentioned algorithms.