3
\$\begingroup\$

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]
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ how to caluculate memmory allocation in O(n) notation \$\endgroup\$ – tessie Sep 19 '16 at 10:34
  • \$\begingroup\$ @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. \$\endgroup\$ – Graipher Sep 19 '16 at 10:36
  • \$\begingroup\$ @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). \$\endgroup\$ – Graipher Sep 19 '16 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.