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 
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.\$\endgroup\$n-2 times and constants are ignored in big-O).\$\endgroup\$