Modified Fibonacci method implementation - dynamic programming

Question

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]

Answer 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

• tessie: how to caluculate memmory allocation in O(n) notation
• Graipher: @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: @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).