Algorithm Ron and Hermione are having a competition to see who can compute the n
ID: 3606694 • Letter: A
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.