Fibonacci Number - Video Solutions

Problem Overview: The task is to compute the nth Fibonacci number. The sequence starts with F(0) = 0 and F(1) = 1. Every next value is the sum of the previous two: F(n) = F(n-1) + F(n-2). Given an integer n, return the value at that position in the sequence.

Approach 1: Recursive Approach (Time: O(2^n), Space: O(n))

The most direct implementation follows the mathematical definition. Call the function recursively for n-1 and n-2, then add their results. Base cases return 0 for n = 0 and 1 for n = 1. While this version is simple, it recomputes the same subproblems repeatedly. For example, calculating F(5) recomputes F(3) and F(2) multiple times. The recursion tree grows exponentially, which leads to O(2^n) time complexity and O(n) call stack space. This approach mainly demonstrates the structure of the recurrence and basic recursion.

Approach 2: Dynamic Programming (Time: O(n), Space: O(n))

The inefficiency in the recursive solution comes from repeated subproblems. Dynamic programming fixes this by storing previously computed Fibonacci values. Build an array where dp[i] stores F(i). Initialize dp[0] = 0 and dp[1] = 1, then iterate from 2 to n and compute dp[i] = dp[i-1] + dp[i-2]. Each Fibonacci number is calculated once, giving linear time complexity O(n). The array requires O(n) additional space. This method removes redundant computation and is the standard bottom‑up DP solution.

An alternative DP variant uses memoization. Instead of building the table iteratively, recursion stores computed results in a cache. Future recursive calls reuse those values instead of recalculating them. Time complexity becomes O(n), matching the iterative DP approach.

Recommended for interviews: Start by explaining the recursive recurrence to show understanding of the sequence definition. Then move to the dynamic programming solution. Interviewers typically expect the O(n) DP approach because it removes exponential recomputation while keeping the implementation straightforward.