Algorithms Two students are having a competition to see who can compute the n th

Question

Algorithms

Two students 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.

student 1 writes the following algorithm:

DynLuc(n) :

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

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

return L[n]

Determine the time and space usage of DynLuc(n). Justify answer please.

Please give a descriptive and "readable" answer. NO SPAM. Thank you.

Explanation / Answer

time usage: since for loop runs n-2 times. Therefore time complexity will be order of O(n).

Since, we are not creating any extra variable or array, L[n] is already intialized in main function (say), Then 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.