Week 5-20 D MAT 243 Online week x D Linear Recurrence Rela x D Mathematical indu

Question

Week 5-20 D MAT 243 Online week x D Linear Recurrence Rela x D Mathematical inductio x D WeBwork Boemer NM x Achvanced Math questi x C Secure I h myasucourses /bbcswebdav/pid-15467123 -dt-conten d-97045656 1/ 9.pdf Q tr asu.edu, 3. Two students, Alex and Casey, wrote Python programs to compute and print the terms a2 to a of the same recursively defined sequence ta 100 Casey's program Alex's program: def a (n. if n 0 return 0 while n 100 elif n 1 2 a b new return 1 else: b new return a (n-1) +2 a (n-2) print (n, new) n 1 for n in range (2,101) print (n, a (n) Both programs are correct and produce the same output, but not with equal computational efficiency. Alex's program finishes practically instantaneously, while Casey's program slows down noticeably when n reaches about 20 to 30 and keeps getting slower with each passing n. a) Explain why Casey's program is inefficient. Give sufficient detail, but do not write more than 100 words. Hint: there are two independent inefficiencies. Identify both. 02017 R. Boerner ASU School of Mathematical and Statistical Sciences 53 PM Ask me anything 4/14/2017

Explanation / Answer

a) Inefficiencies

b) pastebin link for code: https://pastebin.com/thnfQ86n

a_dict = {}
def a(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
if n in a_dict:
return a_dict[n]
else:
res = a(n-1)+2*a(n-2)
a_dict[n] = res
return res

for n in range(2, 101):
print(n, a(n))

c)

a(0) = 0
a(1) = 1
a(n) = a(n-1) + 2*a(n-2) for n > 2

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.