Recursion vs Dynamic Programming

rec-vs-dp.md

Recursive function:

int fib(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return fib(n-1) + fib(n-2);
}

Time complexity is O(fib(n)). The derivation is left as an exercise to the reader.

Dynamic programming version:

int fib(int n) {
    int a[n+1];
    a[0] = a[1] = 1;
    for (int i = 2; i <= n; i++) {
        a[i] = a[i-1] + a[i-2];
    }
    return a[n];
}

Time complexity is O(n).