Design and Analysis of Algorithms20815 marksBasic Algorithms
Write an algorithm to find the nth fibonacci number with its time and space complexity.
Write an algorithm to find the $n^{th}$ fibonacci number with its time and space complexity. [5]
The Fibonacci sequence is defined as: - F(0) = 0 - F(1) = 1 - F(n) = F(n-1) + F(n-2) for n = 2 --- --- Iteration temp = first + second first second i --------------------------------------------------- Initial - 0 1 2 1 0 + 1 = 1 1 1 3 2 1 + 1 = 2 1 2 4 3 1 + 2 = 3 2 3 5 4 2 + 3 = 5 3 5 6 Result:...