6
\$\begingroup\$

I am having trouble with time and complexity analysis. I have done a fibonacci series in a recursive way. I think it is O(n2). 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;
}
\$\endgroup\$
5
  • 2
    \$\begingroup\$ entered 100 got -980107325 \$\endgroup\$ – Parekh Oct 13 '20 at 3:40
  • \$\begingroup\$ Yeah even i got it......guess there is something wrong in this approach.... \$\endgroup\$ – Km Shrikanth Oct 13 '20 at 4:23
  • 2
    \$\begingroup\$ @aryanparekh there is a simple explanation. 100th fibonacci number is beyond the range of both 32 and 64bit integer and so it overflows. \$\endgroup\$ – slepic Oct 13 '20 at 4:32
  • \$\begingroup\$ @AryanParekh Fib(100) is beyond the range of 64 bit integers. \$\endgroup\$ – Martin York Oct 13 '20 at 7:40
  • 1
    \$\begingroup\$ Welcome to Code Review. You are not supposed to change the code in your question after you have received answers, because doing so invalidates the answers. I have thus rolled back your edit. See What should I do when someone answers my question? for more information. \$\endgroup\$ – L. F. Oct 13 '20 at 13:48
7
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Unlike the original algorithm, this algorithm does one extra addition that it doesn't need to. This was introduced when the else if part was eliminated. That isn't a problem in C or C++ where overflow is ignored, but it would be a problem in languages where overflow causes an exception. You can fix this by changing the invariant to n1 == fib(n0-n-1) and n2==fib(n0-n-1) and printing n2 instead of n1. The initializations change to n1=0 and n2=1, since fib(-1) is 1. \$\endgroup\$ – Theodore Norvell Oct 13 '20 at 17:46
  • 1
    \$\begingroup\$ Signed integer overflow is Undefined Behaviour in C and C++! If running under gcc -fsanitize=undefined, that change might well be required to output the largest Fib(n) that fits in an int. If the C+ abstract machine encounters UB at any point during execution of a program, all bets are off for everything before and after that in this run of the program. In practice when compiling for most hardware, signed overflow that isn't visible at compile time won't actually be harmful, but it's very incorrect to say it "isn't a problem" in C++ as a pure language. \$\endgroup\$ – Peter Cordes Oct 14 '20 at 3:39
  • \$\begingroup\$ But other than that, +1, good explanation of transforming between tail-recursion and looping. The OP's code is like a standard iterative implementation, just using tail-recursion to loop. (And the printing is in the base-case, which is super weird vs. returning it.) \$\endgroup\$ – Peter Cordes Oct 14 '20 at 3:53
  • \$\begingroup\$ @PeterCordes You are correct -- the best kind of correct. Thanks for pointing that out. I can't believe that I forgot that int overflow is undefined behaviour in C and C++! \$\endgroup\$ – Theodore Norvell Oct 14 '20 at 19:04
14
\$\begingroup\$

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'

\$\endgroup\$
13
  • 3
    \$\begingroup\$ Very useful insights...Thanks a lot... \$\endgroup\$ – Km Shrikanth Oct 13 '20 at 4:24
  • 5
    \$\begingroup\$ There's nothing wrong with proper tail recursion, such forms are usually transformed into iterative ones by the compiler. \$\endgroup\$ – bipll Oct 13 '20 at 5:56
  • 1
    \$\begingroup\$ @bipll I doubt that, even though it can be true, I don't want to be hanging on the likeliness of "usually". \$\endgroup\$ – Parekh Oct 13 '20 at 6:28
  • 5
    \$\begingroup\$ Tail recursion is simple. Standard optimization. Recursion here is unlikely to be an issue as the depth of the recursion is n. The result of Fib() overflows integers relatively quickly: Fib(300) = 222232244629420445529739893461909967206666939096499764990979600 so for any reasonably n you are not going to overflow the stack of any normal computer. Even though the linear solution (you present) is a better solution its not faster for the reasons you state (which are just wrong) it is faster because the complexity is linear O(n) \$\endgroup\$ – Martin York Oct 13 '20 at 6:44
  • 2
    \$\begingroup\$ @AryanParekh If a true function call is made, yes, but there are many cases where the compiler can avoid the need for that, for example by doing tail recursion, but also by inlining function calls. In general, you are right that if you can write it simply as a for-loop, you should do that, but in some specific cases a seemingly recursive call is more readable and just as performant. \$\endgroup\$ – G. Sliepen Oct 13 '20 at 8:53
7
\$\begingroup\$

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];
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Mathieu Guindon Oct 13 '20 at 17:14
3
\$\begingroup\$

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)\$.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ There is a closed-form for the nth Fibonacci number, so it's O(1) (assuming fixed precision; otherwise with extended precision something like O(log10 Fib(n)) if the cost of operations scales with the number of digits.) en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression. More practically for an exact integer result, in log2(n) iterations using uint64_t multiply and add with this C implementation of the Lucas sequence method. Of course if you want to print every Fib(n), it's of course best to just go iterative \$\endgroup\$ – Peter Cordes Oct 14 '20 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.