Fibonacci Number - Solution
Solutions and explanations
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
return self.fib(n - 1) + self.fib(n - 2)
Complexity Analysis
Here, n is given input.
- Time Complexity:
O(2ⁿ)— due to exhaustive recursive calls. - Space Complexity:
O(n)— due to the recursion stack.
class Solution:
def fib(self, n: int) -> int:
dp = {} # Dictionary for Memoization
def fib_helper(num):
if num <= 1:
return num
if num in dp:
return dp[num]
dp[num] = fib_helper(num - 1) + fib_helper(num - 2)
return dp[num]
return fib_helper(n)
Complexity Analysis
Here, n is given input.
- Time Complexity:
O(n)- Each Fibonacci number from
0tonis computed only once, since memoization avoids redundant computations.
- Each Fibonacci number from
- Space Complexity:
O(n)space is used for the recursion stack and for the memoization cache.
class Solution:
def fib(self, n: int) -> int:
dp = {} # Dictionary for Tabulation
for i in range(n + 1):
if i <= 1:
dp[i] = i
else:
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
Complexity Analysis
Here, n is given input.
- Time Complexity:
O(n)- Each Fibonacci number from
0tonis computed only once, since tabulation avoids redundant computations.
- Each Fibonacci number from
- Space Complexity:
O(n)space is used to store the computed values during tabulation.
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
a, b = 0, 1
for i in range(2, n + 1):
c = a + b
a, b = b, c
return b
Complexity Analysis
Here, n is given input.
- Time Complexity:
O(n)- Each Fibonacci number from
0tonis computed only once.
- Each Fibonacci number from
- Space Complexity:
O(1)- Only constant space is used to store the last two computed values.