big-o order of recursive and iterative fib functions?

Question

I was asked to write a fib function in the most efficient manner?

This is the implementation I provided:

public static int fib(int n)
{
    int prev1 = 1, prev2 = 1, ans = 1, i = 3;

    while (i <= n)
    {
        ans = prev1 + prev2;
        prev1 = prev2;
        prev2 = ans;
        i++;
    }
    return ans;
}

Is this the most efficient? What is the big-o order?

I was also asked to give the big-o notation of a recursive implementation:

public static int recursiveFib(int n)
{
    if (n <= 2)
        return 1;
    else
        return recursiveFib(n-1) + recursiveFib(n - 2);
}

I think this one is exponential 2^n which is why it's inefficient.

Answer 1

Your implementation is O(n), and is the normal way to implement the Fibonacci function. The recursive definition is O(fib(n)) unless memoization or similar is used.

There is also a Closed form expression of the Fibonacci numbers, and This link has some implementations of faster fib functions.

Answer 2

I would say the best way to find fib for a particular n is using the matrix calculation method as given in Link - Page19

where F0 = 0 and F1 = 1. This matrix relation can easlily be used to find the fib for any value of n and n+1. The best part is that is that the multiplying matrix need not be mutliplied n times but only logN times to find the actual value of the Multiplier. Thus the overall compleixty of the algorithm is only O(logN).

The equation is derived from the basic relation of

F1 = 0*F0 + 1*F1

F1 = 1*F0 + 1*F2

Iterating over n the multiplier matrix has to be multiplied n times.