Fibonacci Number

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 - numbers in this series are known as Fibonacci numbers. By definition, each subsequent Fibonacci number is sum of previous two Fibonacci numbers. First two Fibonacci numbers are 0 and 1.

Write a program to efficiently calculate the Nth Fibonacci number.

Time Complexity: O(n)


unsigned int fibonacci(unsigned int n)

{
    unsigned int n1 = 1, n2 = 0;
    unsigned int x, result;
    
    if (n < 2) {
        return n;
    }
    for (x = 2; x <= n; x++) {
        result = n1 + n2;
        n2 = n1;
        n1 = result;
    }
    return (result);
}

On the contrary, a very simple recursive implementation of fibonacci has exponential complexity.


unsigned int fibonacci(unsigned int n)
{
    if (n < 2) {
        return n;
    }
    return (fibonacci(n - 1) + fibonacci(n - 2));
}