Consider the straightforward iterative algorithm for computing the nth Fibonacci numbers (where n is an integer of arbitrary length), as described in the following pseudocode:
create an array F[0...n]
F[0] := 0
F[1] := 1
for i from 2 to n:
F[i] := F[i-1] + F[i-2] // <--- why O(n)?
return F[n]
Can someone explain why, according to my algorithms course, this algorithm has time complexity O(n^2)?
In particular, why does the marked step above have time complexity O(n) (according to my algorithms course) as opposed to O(1) even though it's just an addition of two integers?
Or was I given wrong information?