CODEWITHSUNDEEP
complexity-theoryfibonacci
John Doe
John Doe

Reputation: 45

Order of complexity of fibonacci functions

I have the following three algorithms that give the Fibonacci numbers. I would like to know how I would be able to find out each of their order of complexity. Does anyone know how I might be able to determine this?

Method 1
------------------------------------------------------------------------
long long fibb(long long a, long long b, int n) {
    return (--n>0)?(fibb(b, a+b, n)):(a);
}

Method 2
------------------------------------------------------------------------
long long int fibb(int n) {
    int fnow = 0, fnext = 1, tempf;
    while(--n>0){
        tempf = fnow + fnext;
        fnow = fnext;
        fnext = tempf;
        }
        return fnext;   
}

Method 3
------------------------------------------------------------------------
long long unsigned fib(unsigned n) {
    return floor( (pow(PHI, n) - pow(1 - PHI, n))/sqrt(5) );
}

Correct me if I am wrong, but my guess would be that method one is O(2^n) since it is recursive, medtod 2 will be O(n) and the last one will be O(1).

Upvotes: 0

Views: 74

Answers (1)

chqrlie
chqrlie

Reputation: 144951

Methods 1 and 2 have complexity O(n). The reasons are straightforward:

  • Method 1 recurses exactly n-1 times, each recursion performs a simple arithmetic operation.
  • Method 2 iterates exactly n-1 times, each iteration has constant time, simple math again.

Method 3 has indeed a complexity of O(1), but may not compute the correct value, merely an approximation.

Upvotes: 1

Related Questions