The first two numbers in the Fibonacci sequence are 1 and 1. Every additional number in the sequence is the sum of the two previous numbers. The first six numbers of the Fibonacci sequence are 1, 1, 2, 3, 5 and 8.
Check for the fibonacci number
getFib function that takes a number
n as a parameter and returns the nth Fibonacci number. If
n is zero, zero should be returned.
Sample Input and Output
Input: 4 Output: 3
Try solving the problem using memoization and tabulation.
How much faster was the problem solved? How can you account for this in terms of time complexity? How about matrix exponentiation and fast doubling?