Optimized Fibonacci Sequence in TypeScript with O(1) Space Complexity

Efficiently Calculate the nth Fibonacci Number Using Constant Space

Problem Overview: Fibonacci Sequence with O(1) Space Complexity

The problem requires implementing the fib(n) function to return the nth number in the Fibonacci sequence using only O(1) space complexity.

Fibonacci Sequence Recap:

The Fibonacci sequence is defined as:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n−1) + F(n−2) for n ≥ 2

Given that the Fibonacci sequence grows exponentially, the challenge lies in efficiently calculating F(n) without consuming extra space.

Constraints:

  • We must achieve O(1) space complexity.
  • The time complexity should ideally be O(n).

Solution Approach:

To achieve O(1) space, we can iteratively compute the Fibonacci numbers while only storing the last two computed values. This eliminates the need for storing the entire sequence.

Steps:

  1. Base Cases : Directly return the value for n = 0 and n = 1.
  2. Iterative Calculation : Use a loop to calculate the nth Fibonacci number by updating the previous two values iteratively.

TypeScript Implementation:

function fib(n: number): number {
    if (n === 0) return 0; // Base case F(0)
    if (n === 1) return 1; // Base case F(1)

    let prev2 = 0; // F(0)
    let prev1 = 1; // F(1)

    for (let i = 2; i <= n; i++) {
        let current = prev1 + prev2; // F(i) = F(i-1) + F(i-2)
        prev2 = prev1; // Update F(i-2)
        prev1 = current; // Update F(i-1)
    }

    return prev1; // Return the nth Fibonacci number
}

Explanation:

  • Base Cases : The function checks if n is 0 or 1 and returns the corresponding Fibonacci number immediately.
  • Iterative Loop : Starting from 2 to n, the loop calculates the current Fibonacci number as the sum of the previous two numbers.
  • Update : After calculating the current Fibonacci number, the previous two numbers are updated for the next iteration.
  • O(1) Space: This approach only uses two variables, ensuring constant space usage.

Alternative Solutions:

  • Matrix Exponentiation : This method can compute Fibonacci in O(log n) time but is more complex and typically requires more space.
  • Binet’s Formula : Using a direct formula involving the golden ratio. While it offers O(1) space, it suffers from precision issues with large n due to floating-point arithmetic.

Conclusion:

The provided solution is the most efficient in terms of both time and space for large values of n. It ensures a straightforward implementation with minimal memory usage, making it ideal for environments with tight space constraints.

If you like this, please think about buying me a coffee! ☕️.

Burhanuddin’s Code Compendium

Thank you for being a part of the Burhanuddin’s Code Compendium community! Before you go: