Consider the famous fibonnaci sequence problem:
https://leetcode.com/problems/fibonacci-number
The brute force approach is 2^n. We can verify this by drawing a tree and seeing that nodes exponentially grow each level:
class Solution:
def fib(self, N: int) -> int:
if N <= 1:
return N
return self.fib(N - 1) + self.fib(N - 2)But what about the memoized solution? How do we calculate its time. Is there a generic way that the time complexity transforms when you introduce caching?
class Solution:
def fib(self, N: int) -> int:
if N <= 1:
return N
cache = [0] * (N + 1)
cache[1] = 1
for i in range(2, N + 1):
cache[i] = cache[i - 1] + cache[i - 2]
return cache[N]Solution says its o(n)
Comments (0)