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