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.
Write a getFib function that takes a number n as a parameter and returns the nth Fibonacci number. If n is zero, zero should be returned.
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?