# Modified Fibonacci method implementation - dynamic programming

I found this question on Hackerrank in dynamic programming:

Define a modified Fibonacci sequence as: $$t_{n+2} = t_n + t_{n+1}^2$$

Given three integers, $t_1$, $t_2$, and $n$, compute and print term $t_n$of a modified Fibonacci sequence.

Could this efficiency be improved?

t1,t2,n = map(int, raw_input().split(" "))
array =[]
array = array+[t1, t2]
for i in range(2,n):
ele = array[i-2] + array[i-1]*array[i-1]
array.append(ele)
print array[n-1]


Making the array initialization better:

t1,t2,n = map(int, raw_input().split(" "))
array = [t1, t2]
for i in range(2,n):
ele = array[i-2] + array[i-1]*array[i-1]
array.append(ele)
print array[n-1]


Currently your code needs $\mathcal{O}(n)$ memory, because you keep all terms. It would be more efficient to just save $t_{n-1}$ and $t_{n-2}$ and update them every loop, using tuple assignment:

t1, t2, n = map(int, raw_input().split())
for _ in range(2, n):
t1, t2 = t2 + t1**2, t1
print t2 + t1**2

• how to caluculate memmory allocation in O(n) notation – tessie Sep 19 '16 at 10:34
• @tes I don't have general guidelines for this. But it is quite obvious that a list of length n takes up $\mathcal{O}(n)$ space because every element of the list must be saved. How big each element of the list is depends on its type and does not matter to big-O notation. – Graipher Sep 19 '16 at 10:36
• @tes In contrast, my code only ever has three variables defined, regardless of n, so is $\mathcal{O}(1)$ in memory (and $\mathcal{O}(n)$ in time, because it needs to run the loop n-2 times and constants are ignored in big-O). – Graipher Sep 19 '16 at 11:45