Fibonacci Sequence

Problem Statement

Given an integer n, return the nth number in the Fibonacci sequence. The sequence is defined as:

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n > 1

Example: Input: n = 6, Output: 8

Approach 1: Recursion

Explanation: Direct recursive definition of Fibonacci.

Time Complexity: O(2n)

Space Complexity: O(n) recursion stack

function fib(n):
    if n == 0: return 0
    if n == 1: return 1
    return fib(n-1) + fib(n-2)

Approach 2: Memoization (Top-Down DP)

Explanation: Store results of subproblems to avoid recomputation.

Time Complexity: O(n)

Space Complexity: O(n)

memo = [-1]*(n+1)
function fib(n):
    if n == 0: return 0
    if n == 1: return 1
    if memo[n] != -1: return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

Approach 3: Tabulation (Bottom-Up DP)

Explanation: Build DP array iteratively.

Time Complexity: O(n)

Space Complexity: O(n)

dp[0] = 0
dp[1] = 1
for i = 2 to n:
    dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Approach 4: Space Optimized DP

Explanation: Only store last two values to save space.

Time Complexity: O(n)

Space Complexity: O(1)

a = 0, b = 1
for i = 2 to n:
    c = a + b
    a = b
    b = c
return b
Flowchart