Dynamic Programming Fibonacci algorithm

Question

I'm working on an algorithm to calculate a Fibonacci number and got the pseudo code for it but I can't figure out how much time it takes to run. I think it runs at O(n) but not quite sure. Here is the code:

Algorithm Fast-Fibonacci(n)
Let fib[0] and fib[1] be 1.
for each i from 2 to n, do:
    Let fib[i] be fib[i - 2] + fib[i - 1].
end of loop
return fib[n].

Thanks for any help.

Answer 1

You are correct that this takes O(n) as you are just counting sequentially from 2 to n to fill your array. If you were doing some sort of lookup for each of the i-1 and i-2 numbers, that could increase complexity, but the way you have written it, you are calling a direct address for each of those values.