Fibonacci Numbers
Easy
Write a function fib(n) that returns the nth Fibonacci number. The Fibonacci sequence is defined as F(n) = F(n-1) + F(n-2) with F(0) = 1 and F(1) = 1, which produces the following pattern:
1, 1, 2, 3, 5, 8, 13 ...
Examples
Pythonfib(0) # => 1 fib(1) # => 1 fib(2) # => 2 fib(3) # => 3 ... fib(10) # => 89 fib(20) # => 10946
This question is a classic example of how dynamic programming, or memoization, can help us solve problems faster by reducing repetitive computations.
In this first version, we recursively call the fib function twice, and then we call it twice more in every subsequent recursive call, so the total number of operations expands to O(2^n)!
To improve the runtime of our program, let's save our prior calculations in a dictionary called memo and pass it into our function. Now, if we've already found fib(n) before, our function will use this stored value instead of recursing again.
Time Complexity: The time complexity of the memoized version is O(n). This is because each Fibonacci number from 0 to n is computed only once and then stored in the memo dictionary. The recursive calls will now simply look up the value in the dictionary if it has already been computed, reducing redundant calculations.
Space Complexity: The memo dictionary stores each Fibonacci number from 0 to n, which requires O(n) space.
Interview experiences
1 sharedRelated courses
