101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 4 main approaches to solve this problem:

  1. Naive Recursive Approach - Complex approach
  2. Memoization (Top-Down Dynamic Programming) - Complex approach
  3. Tabulation (Bottom-Up Dynamic Programming) - Complex approach
  4. Space-Optimized Iterative Approach - Complex approach

Approach 1: Naive Recursive Approach

The naive recursive approach directly implements the mathematical definition of the Fibonacci sequence: F(n) = F(n-1) + F(n-2). While this approach is intuitive and easy to understand, it has exponential time complexity due to redundant calculations.

Algorithm:

  1. Define base cases: F(0) = 0 and F(1) = 1.
  2. For n > 1, return F(n-1) + F(n-2), calculated recursively.
  3. The recursion will continue until it reaches the base cases, then unwind to compute the final result.

Time Complexity:

O(2^n)

Each call branches into two recursive calls, leading to exponential growth in the number of function calls.

Space Complexity:

O(n)

The recursion stack will have at most n frames, each using constant space.

Approach 2: Memoization (Top-Down Dynamic Programming)

The memoization approach optimizes the recursive solution by storing the results of subproblems to avoid redundant calculations. This is a top-down dynamic programming approach that significantly improves efficiency.

Algorithm:

  1. Create a memoization table (array or hash map) to store computed Fibonacci numbers.
  2. Define base cases: F(0) = 0 and F(1) = 1.
  3. Before calculating F(n) recursively, check if it's already in the memoization table.
  4. If it's in the table, return the stored value; otherwise, calculate it recursively and store the result in the table.
  5. Return the final result from the table.

Time Complexity:

O(n)

Each Fibonacci number is calculated exactly once and then stored for future use.

Space Complexity:

O(n)

We need to store all Fibonacci numbers from F(0) to F(n) in the memoization table.

Approach 3: Tabulation (Bottom-Up Dynamic Programming)

The tabulation approach is a bottom-up dynamic programming solution that builds the Fibonacci sequence iteratively from the base cases up to the desired number. This approach avoids recursion entirely and is typically more efficient in terms of space.

Algorithm:

  1. Create a table (array) to store Fibonacci numbers from F(0) to F(n).
  2. Initialize the base cases: F(0) = 0 and F(1) = 1.
  3. Iterate from i = 2 to n, calculating F(i) = F(i-1) + F(i-2) and storing it in the table.
  4. Return F(n) from the table.

Time Complexity:

O(n)

We perform a single calculation for each Fibonacci number from F(2) to F(n).

Space Complexity:

O(n)

We need to store all Fibonacci numbers from F(0) to F(n) in the table.

Approach 4: Space-Optimized Iterative Approach

The space-optimized iterative approach recognizes that we only need the two previous Fibonacci numbers to calculate the next one. This allows us to reduce the space complexity to O(1) while maintaining O(n) time complexity.

Algorithm:

  1. Initialize variables a = 0 (F(0)) and b = 1 (F(1)).
  2. For i = 2 to n, calculate the next Fibonacci number as a + b.
  3. Update a to be b and b to be the newly calculated Fibonacci number.
  4. After the loop, b will contain F(n).

Time Complexity:

O(n)

We perform a single calculation for each Fibonacci number from F(2) to F(n).

Space Complexity:

O(1)

We only need to store two Fibonacci numbers at any time, regardless of the input size.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
function fibonacci(n):
    // Base cases
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2)
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone