Algorithm Ron and Hermione are having a competition to see who can compute the n

Question

Algorithm

Ron and Hermione are having a competition to see who can compute the nth Lucas number Lnmore quickly, without resorting to magic. Recall that the nth Lucas number is defined as Ln= Ln1 + Ln2 for n > 1 with base cases L0 = 2 and L1 = 1. Ron opens with the classic recursive algorithm:

FasterLuc(n) :

a = 2,    b = 1

for i = 2 to n

c = a + b

a = b

b = c

end

return a

Find the BUG in the algorithm and correct the mistake. Then determine the time and space of the algorithm. Justify your claims please. NO SPAM

Explanation / Answer

While returning it should be c inplace of a that is, we should return c in order to get correct answer.

Since, for loop runs for n-2 times. therefore time complexity is order of O(n).

Since, no extra variable is created. Therefore space complexity will be O(1).

Hope it helps, do give your valuable response.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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