Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is:

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

Given 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.

## Fibonacci Numbers

This problem asks us to calculate the nth Fibonacci number, F(n), where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1.

### 1. Naive Recursive Solution

The most straightforward approach is to directly implement the recursive definition.

```python
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Example usage
n = 4
result = fibonacci_recursive(n)
print(f"F({n}) = {result}") # Output: F(4) = 3

2. Optimal Solution: Dynamic Programming (Iterative)

A more efficient solution uses dynamic programming to avoid redundant calculations. We can store the previously computed Fibonacci numbers in an array or simply use two variables to keep track of the last two Fibonacci numbers.

def fibonacci_dp(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Example usage
n = 4
result = fibonacci_dp(n)
print(f"F({n}) = {result}") # Output: F(4) = 3

3. Big(O) Run-time Analysis (Recursive)

• The recursive solution has a time complexity of O(2^n). Each call to fibonacci_recursive(n) makes two more calls, resulting in an exponential increase in computations as n grows. This is because the same Fibonacci numbers are recalculated multiple times.

4. Big(O) Space Usage Analysis (Recursive)

• The recursive solution has a space complexity of O(n) due to the call stack. In the worst case, the maximum depth of the recursion is n, which means the call stack will hold n function calls.

5. Big(O) Run-time Analysis (Dynamic Programming)

• The dynamic programming solution has a time complexity of O(n). The loop iterates from 2 to n, performing a constant amount of work in each iteration.

6. Big(O) Space Usage Analysis (Dynamic Programming)

• The dynamic programming solution has a space complexity of O(1). We are only using two variables (a and b) to store the last two Fibonacci numbers, so the space used does not depend on the input size n.

7. Edge Cases

• n = 0: The function should return 0.
• n = 1: The function should return 1.
• n > 30: While the problem statement constrains n <= 30, for larger values of n, consider using a language with arbitrary-precision arithmetic to avoid integer overflow.

Code with Arbitrary-Precision Arithmetic (Python)

If we want to handle larger values of n beyond the constraint (n <= 30) without risking integer overflow, Python's built-in arbitrary-precision arithmetic comes in handy. Here's how you can modify the dynamic programming solution:

def fibonacci_large_n(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Example usage with a larger n
n = 50
result = fibonacci_large_n(n)
print(f"F({n}) = {result}")

In this modified version, Python automatically handles the growing integer sizes, preventing overflow.