This is a two part question. It should read (b) for the DynLuc(n) function. Than

Question

This is a two part question. It should read (b) for the DynLuc(n) function. Thanks in advance!

DynLuc(n): L [0] = 2, L [1] = 1 for i = 2 ton {L[i] = L[i-1] + L[i-2]} return L [n] Determine the time and space usage of DynLuc (n). Justify your answers and compare them to the answers in part (4a). With a gleam in her eye, Hermione tells Ron that she can do everything he can do better: she can compute the nth Lucas number even faster because intermediate results do not need to be stored. Over Ron's pathetic cries, Hermione says FasterLuc(n): a = 2, b = 1 for i = 2 ton c = a + b a = b b = c end return a Ron giggles and says that Hermione has a bug in her algorithm. Determine the error, give its correction, and then determine the time and space usage of FasterLuc(n). Justify your claims.

Explanation / Answer

given :

DynLuc(n):

L[0]=2, L[1]=1

for i = 2 to n { L[i]= L[i-1]*L[i-2]}

return L[n]

Time complexity:

in this alogrithm the for loop runs from 2 to n, means n-1 times... so the complexity would be O(n)

Space complexity:

here additionally an array L is used, which is not actually passed, if L is not globally declared then the space complexity would be O(n).. other wise O(1)

c)

FasterLuc(n):

a=2,b=1

for i=2 to n

c= a+b

a = b

b = c

end

return a

Error is :

a=b

b=c

you need write it as

b=a

a=c

Corrected algorithm:

FasterLuc(n):

a=2,b=1

for i=2 to n

c= a+b

b=a

a = c

end

return a

Time complexity:

in this alogrithm the for loop runs from 2 to n, means n-1 times... so the complexity would be O(n)

Space complexity:

O(1)// for variable declarations

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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