Recurrence relation from code

Question

My Friends, Hi,

I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code:

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

this find a n-th Fibonacci number. ftab is one-dimensional array that all of elements at first is -1.

any hints or discuss is highly appreciated.

Answer 1

This Dynamic Programming algorithm uses an array of length $n$. Filling in any element of this array takes constant time, since any element other than the two base cases can be computed by simply accessing the previous two elements. Thus, since each element is the array is computed at most once in constant time, it follows that computing the entire array takes $O(n)$ time. After doing this, we simply return the last element, which again takes constant time. So the overall time complexity is $O(n)$, which also happens to be the space complexity.

[As an aside, note that it's possible to reduce the space complexity to be $O(1)$ while keeping the same time complexity.]