Below is a snapshot of how this works
Consider my f[] array is as below
What this code does is, it does not store value for fib(0) and fib(1), rather it stores values of fib(n) for $n \geq2$
in f[n-2].
So, for Fib(2), the value is stored in f[0], for Fib(3), the value is stored in f[1] and so so...
Consider I have invoked Fib(10)
Below is the execution sequence
Now, it looks like the time complexity for this program will be $2^n$, but it's not.
When, the recursion will bottom out and start to trace back, it will use the values from the table for the repeated function calls involved.
Like at last, for Fib(2), it calls Fib(1)+Fib(0) and it gets resolved without further recursion and value returned is 2 and it is stored in f[0].
Now, when recursion goes back
for fib(3)=fib(2)(return value 2)+fib(1)(gives 1)=3 and stored in f[1]=3 and 3 returned to the caller fib(4).
Then we go back
fib(4)=fib(3)(return value 3)+fib(2) (Now this fib(2) will use value from the table f[2-2]=f[0]=2)=3+2=5 stored in f[4-2]=f[2]=5.
And it goes on untill it finally evaluated fib(10).
So, number of function calls made for fib(10)=19
So, for fib(n) number of function calls would be $2n-1$
So, time complexity $\theta(n)$
Code : https://ideone.com/HciGrW