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.
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.
Yep. The big giveaway is that you have a constant number of operations per loop and the size of your loop is linear against the size of n.
A more space-efficient solution exists, however, since you don't particularly care about any numbers other than the last two. Try that next!
Iterative solution to find the nth fibonnaci takes O(n) in terms of the value of n and O(2^length(n)) in terms of the size of n ( length(n) == number of bits to represent n). This kind of running time is called Pseudo-polynomial. However, if recursive method is used to find the fib of n, then it will take exponential time in terms of the value(O(2^n)). But this can be reduced by using dynamic programming approach to solve the fib of n.
