Lesson

14.3Fibonacci Sequence

Problem Statement

The Fibonacci numbers, commonly denoted as F(n), form a sequence called the Fibonacci sequence. Each number in the sequence is the sum of the two preceding ones, starting from 0 and 1. Mathematically, it is defined as:

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

Given an integer n, calculate F(n).

Example 1

Input: n = 2
Output: 1
Explanation:
F(2) = F(1) + F(0) = 1 + 0 = 1

Example 2

Input: n = 3
Output: 2
Explanation:
F(3) = F(2) + F(1) = 1 + 1 = 2

Example 3

Input: n = 4
Output: 3
Explanation:
F(4) = F(3) + F(2) = 2 + 1 = 3

Constraints

0 <= n <= 30

Approach

a. Brute Force (Recursive)

Steps:

Base Cases:
- If n == 0, return 0.
- If n == 1, return 1.
Recursive Case:
- For n > 1, compute F(n) by recursively calculating F(n-1) and F(n-2), then summing them up.
Implementation:
- Implement the above logic using a simple recursive function without any optimizations.

Time & Space Complexity:

Time Complexity: O(2ⁿ)
Each function call generates two more calls, leading to an exponential number of calls as n increases.
Space Complexity: O(n)
The maximum depth of the recursion stack is n.

Code Snippet:

Dry Run:

Let's perform a dry run for n = 4.

So, F(4) = 3.

b. Optimized Approach (Dynamic Programming - Memoization)

Steps:

Base Cases:
- If n == 0, return 0.
- If n == 1, return 1.
Memoization:
- Create a memo object to store previously computed Fibonacci numbers.
- Before computing F(n), check if it exists in the memo. If it does, return the stored value to avoid redundant calculations.
Recursive Case with Memoization:
- For n > 1, compute F(n) by summing F(n-1) and F(n-2), storing each result in the memo.
Implementation:
- Implement the above logic using a recursive function enhanced with memoization.

Time & Space Complexity:

Time Complexity: O(n)
Each Fibonacci number up to n is computed once and stored in the memo.
Space Complexity: O(n)
The memo object stores results for each n, and the recursion stack can go as deep as n.

Code Snippet:

Dry Run:

Let's perform a dry run for n = 4 with memoization.

So, F(4) = 3.

Complexity Analysis

Brute Force Time & Space:
- Time Complexity: O(2ⁿ)
  The recursive solution explores all possible combinations of previous Fibonacci numbers, leading to an exponential number of function calls.
- Space Complexity: O(n)
  The recursion stack can go as deep as n, requiring linear space.
Optimized Time & Space (Memoization):
- Time Complexity: O(n)
  Each Fibonacci number up to n is calculated once and stored in the memo, preventing redundant calculations.
- Space Complexity: O(n)
  The memo object stores the result for each n, and the recursion stack can go as deep as n, requiring linear space.

Conclusion

When solving problems like calculating Fibonacci numbers, it's crucial to choose the right approach based on the problem's constraints and requirements.

Brute Force (Recursive):
- Pros: Simple and easy to implement.
- Cons: Highly inefficient for larger values of n due to its exponential time complexity and redundant calculations.
Optimized Approach (Dynamic Programming - Memoization):
- Pros: Significantly reduces time complexity by storing and reusing previously computed results.
- Cons: Requires additional space for the memo object.

Key Takeaways:

Brute Force methods are straightforward but often impractical for large inputs due to inefficiency.
Dynamic Programming (Memoization) enhances the brute force approach by eliminating redundant computations, making it suitable for larger and more complex problems.
Always analyze whether a problem has an optimal substructure and overlapping subproblems to determine if Dynamic Programming can be applied effectively.
Understanding and implementing optimized solutions not only improves performance but also demonstrates a deeper grasp of algorithmic principles, which is essential for programming and technical interviews.

Choosing the right problem-solving technique ensures efficient and effective solutions, paving the way for tackling more complex challenges with confidence.

Previous Next