A Fibonacci series

Question

I am having trouble with time and complexity analysis. I have done a fibonacci series in a recursive way. I think it is O(n²). Can you find out the time analysis? If possible, could you elaborate it?

#include<iostream>
using namespace std;

void fibonacci(int n,int n1,int n2)
{
    if(n==0)
    {
        cout<<endl<<n1;
        return;
    }
    else if(n==1)
    {
        cout<<endl<<n2;
        return;
    }
    fibonacci(n-1,n2,n1+n2);
    return;
}

int main()
{
    int n;
    cout<<"Enter the number:"<<endl;
    cin>>n;
    fibonacci(n,0,1);
    return 0;
}

Answer 1

I'm not sure any of the answers have yet really addressed the complexity. I'm going to do that by transforming your algorithm into one that is simpler without changing the time complexity. This both proves the time complexity and also gives you a version of the algorithm that might be easier to read and reason about.

Let's start with your solution

void fibonacci(int n,int n1,int n2)
{
    if(n==0)
    {
        cout<<endl<<n1;
        return;
    }
    else if(n==1)
    {
        cout<<endl<<n2;
        return;
    }
    fibonacci(n-1,n2,n1+n2);
    return;
}

The else if part isn't really needed, so let's delete that and also get rid of the superfluous return commands. [See the comments for discussion of why this step isn't quite as innocent as it seems.]

void fibonacci(int n,int n1,int n2)
{
    if(n==0) {
        cout<<endl<<n1; }
    else { 
        fibonacci(n-1,n2,n1+n2); }
}

Reverse the if. Also I'm going to put back one of those returns and take the printing out of the else part.

void fibonacci(int n,int n1,int n2)
{
    if(n!=0) {
        fibonacci(n-1,n2,n1+n2);
        return ; }
    cout<<endl<<n1;
}

Apply tail recursion optimization --- i.e., replace the recursive call and the following return with a reassignment of the parameters and a jump to the start of the subroutine. This step will change the space complexity,* but not the time complexity.

void fibonacci(int n,int n1,int n2)
{
    start: 
    if(n!=0) {
        int sum = n1+n2 ;
        n1 = n2 ;
        n2 = sum ;
        n = n-1 ;
        goto start ; }
    out<<endl<<n1;
}

Use a loop instead of a goto.

void fibonacci(int n,int n1,int n2)
{
    while(n!=0) {
        int sum = n1+n2 ;
        n1 = n2 ;
        n2 = sum ;
        n = n-1 ; }
    cout<<endl<<n1;
}

You don't really need the parameters to be parameters. I'd probably document the subroutine, so it's clear what it does. And I'd document the while loop with an invariant, so it's more clear how it works.

void fibonacci(int n)
// Precondition: n >= 0
// Postcondition: the value of fib(n) has been printed to standard out
//                preceded by an end of line.
{
    int n1 = 0 ;
    int n2 = 1 ;
    // Let n0 be the original value if n.
    // invariant n1 == fib( n0-n ) and n1 == fib(n0-n+1) 
    while(n!=0) {
        int sum = n1+n2 ;
        n1 = n2 ;
        n2 = sum ;
        n = n-1 ; }
    cout<<endl<<n1;
}

(And also change the place where it's called, course.)

At this point, it's clear (I think) that the algorithm is O(n). None of the transformations change the time complexity, so the time complexity of the original is also O(n).

(*) That is, it will change the space complexity from O(n) to O(1) unless your compiler does tail-recursion optimization. If it does, the space complexity was O(1) from the start.

Answer 2

About using namespace std

You should try to avoid this statement as it is considered bad practice. It is best to avoid it whenever you can. Here is a simple example why.

#include <iostream>
#inlcude <list>

using namespace std;

class list // uh-hoh, list is already defined, or is that std::list?
{     
    ...
};

Another problem is that if you have this in any of the header files in your project, you will be forced to use this in any file you have included the header.

Why is using namespace std considered bad practice

Template meta-programming

This moves the calculation from run-time to compile-time. Your program will take a little longer to compile, but the complexity will be O(1). It uses templates in C++ to force the compiler to calculate the value.

This is another option to approach this problem and the fastest way since this moves calculation to compile time.

However, the drawback is that you cannot use values that aren't known at compile time. For example, you could find the value for 5 but not something the user will enter, or for example a random number generated.

#include<iostream>

template <unsigned N>
struct Fibonacci
{
    enum : uint64_t
    {
        value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
    };
};

template <>
struct Fibonacci<1>
{
    enum
    {
        value = 1
    };
};

template <>
struct Fibonacci<0>
{
    enum
    {
        value = 0
    };
};

int main()
{
    std::cout << Fibonacci<20>::value;
}

This method will be the fastest but will only work if your numbers are constant.
Template meta-programming in C++

Replace recursion with iteration

Although recursion makes your code a little cleaner, recursion almost always runs slower, this is because for each call it needs allocation of a new stack frame
Due to the fact that space in the stack is finite, there is a limit to how many recursive calls you can make, before C++ gives you 0xC00000FD. Which is stack overflow
With a few more lines of code, you can replace recursion with this scenario and make it much faster, without this problem.
This doesn't mean that you shouldn't use recursion, some algorithms need recursion, but if you can replace it with iteration, then it's worth.

Here it is with iteration.

uint64_t fibonacci(int n)
{
    uint64_t n1 = 0,n2 = 1,n3 = 1;
    if (n == 1 || n == 0) return 0;
    else if(n == 2) return 1;

    for (int i = 2;i < n;++i)
    {
        n3 = n1 + n2;
        n1 = n2;
        n2 = n3;
    }
    return n3;
}

'\n' over std::endl

'\n' and std::endl will both accomplish your task, but std::endl calls std::flush every time and flushes the stream, this is why it will be slower, than simply printing '\n'

Comparison between std::endl and '\n'

Answer 3

The most obvious way to write fib:

int fib(int n)
{
    if (n < 2) // 0 or 1
    {
        return 1;
    }
    return fib(n-1) + fib(n-2);
}

You can see it explodes because for every call to fib() you get 2 subsequent calls which both get 2 calls with all get 2 calls etc.

      Level               Calls                 Calls  This Level    Total Calls
    Level n                   1                        1                 1
    Level n-1            1         1                   2                 3
    Level n-2          1   1      1   1                4                 7
    Level n-3         1 1 1 1    1 1 1 1               8                 15

So the complexity of Fib is Fib!!!!!
More exactly Complecity is O(2Fib(n)-1)
but removing constants O(Fib(n))

Lets write some code to validate this:

int fibComplexity(int n)
{
     // has the same properties of fib.
     // but returns the number of calls rather than the value.
     if (n < 2)
     {
         return 1;      // You called this function once.
     }
     return 1           // the call to this function.
            + fibComplexity(n-1)  // Count of calls in this tree
            + fibComplexity(n-2)  // Count of calls in this tree.
}

If we runt this:

int main()
{
    for(int loop = 2; loop < 15; ++loop)
    {
        std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << "\n";
    }
}

Generates: ( added formatting)

n  F   O
2  2   3     
3  3   5
4  5   9
5  8   15
6  13  25
7  21  41
8  34  67
9  55  109
10 89  177
11 144 287
12 233 465
13 377 753
14 610 1219   O = 2f-1

---

But every coding course you take will then ask you to make a linear based solution.

What you present above is a recursive (but linear solution). Most people would have gone for a loop based linear solution (but there is no difference). The complexity is exactly the same.

What you done is recursively call the function adding things up as you go. Each call makes exactly one additionally call but only to a depth of n. Then it returns.

So you have complexity of O(n).

---

But you can take this one step further. The fib algorithm can easily be implemented as O(1).

This is because fib quickly outstrips the size of an integer (even long long). You can easily pre-calulcate all the valid values that can be stored in a variable and put them in an array. Then simply return the value by looking up the result:

int fib(int n) {
    static const int fibValue[] = { ... };
    if (n < 0 || n > std::size(fibValue)) {
        // This is 47 for 32 bit ints
        //         93 for 64 bit ints
        throw "Result out of range"
    }
    return fibValue[n];
}

Answer 4

Just to be explicit: You are \$O(n)\$ in time and \$O(n)\$ in memory. I don't believe you can easily do better in integer arithmetic (when actually calculating it) in time, but memory could be \$O(1)\$.

As has been pointed out by Peter Cordes, there is a "Closed form" for the Fibonacci sequence, which means that if you have a constant time infinite precision floating point system, you can achieve \$O(1)\$. Computer floating point can achieve an approximation, but I think you will get more accurate results with integer math.

As also pointed out by Peter Cordes, there is a "Lucas sequence method" that can do \$O(\log{n})\$ given integer multiplication and a fair bit more complexity.

If you use your function iteratively to print the Fibonacci sequence, your time result would be \$O(n^2)\$, and that can be done in \$O(n)\$.