So I was writing a program to implement the following task. For any value of n greater than or equal to 2, F(n) equals the sum of F(n-1) and F(n-2), where F(x) returns the sum of all elements in a fibonacci series of length x.
For example, F(4) would equal F(3) + F(2). Now, F(3) is 0, 1, 1; which sums to 2; and F(2) is 0,1; which sums to 1. Thus, F(4) = F(3) + F(2) = 2 + 1 = 3. Now, this is the original algorithm I came up with. Now, turns out that this algorithm is perfectly applicable for small values of n, say upto 30. However, the ‘runtime cost’ of this algorithm is exponential, which is why I wanted to try out the iterative approach as well (linear runtime cost).
# fibonacci sequence --> 0 1 1 2 3 5 8 13 21
def fibonacci(n):
# f(n) = f(n-1) + f(n-2) where n > 1
a, b = 0, 1
if n == 0:
return a
elif n == 1:
return b
elif n > 1 and n < 30:
return fibonacci(n-1) + fibonacci(n-2)
else:
return 'n should be between 2 and 29'
print (fibonacci(6)) # input here
# methodology, every time, f(n) breaks down further and further
# eg. f(4) = f(3) + f(2)
# = f(2) + f(1) + f(1) f(0) not written because it is = 0, no effect on output
# = f(1) + 2f(1)
# = 3f(1)
The above approach, or rather the one I originally came up with, has a runtime cost of O(2^n). How?
F(n) => F(n – 1) + F(n – 2) + c.
% c is a constant. for the exercise above, it is = 0.
% we can assume both to be approximately equal F(n – 1) ~= F(n – 2)
F(n) => F(n – 2) + F(n – 2) + c
=> 2F(n – 2) + c (F(n – 2) = F(n – 3) + F(n – 4) + c ~= 2F(n – 4) + c
=> 2( 2F(n – 4) +c) +c
=> 4F(n – 4) + 3c
repeat process
=> 4(2F(n – 6) + c) + 3c
=> 8F(n – 6) + 7c
now, set 2^k = T, where T is the coefficient of F(n-…). T = 8 above *eg.
F(n) ==> 2^k * F(n – 2k) + (2^k – 1)c
Now, we will set n – 2k equal to 0. This means that k should equal n/2. Thus, the equation simplifies as follows and the exponential cost is revealed.
k = n / 2
F(n) ==> 2 ^ (n / 2) * F(0) + 2 ^ (n / 2) * c
This simplifies to 2 ^ (n / 2), as other elements can be approximated to having either no cost, or a constant cost that does not change with n. This means that the cost of the algorithm is O(2 ^ (n / 2)), which shows that it increases exponentially with n.
To avoid an exponentially increasing cost, we can adopt an iterative approach, which avoids stacking function calls on top of each other as in a recursive approach.
def fibs(n): # iterative approach
fibs = [0, 1, 1]
for f in range(2, n):
fibs.append(fibs[-1] + fibs[-2])
return fibs[n]Now, the cost of this algorithm is O(n), as it will only be executed n times, or rather n – 2 times to be exact, as the for loop starts iterating from 2, so as to avoid touching the values that correspond to f(0), f(1), and f(2). To conclude, the iterative algorithm is simpler and much more efficient for large values of n.
https://stackoverflow.com/questions/15047116/an-iterative-algorithm-for-fibonacci-numbers this post on stack overflow dives deeper into the implementation of the iterative algorithm.