Day 56: Python Fibonacci nth Term – Blazing Fast O(n) Iterative Solution with O(1) Space (No Recursion!)

Source: Dev.to

Overview

Welcome to Day 56 of the #80DaysOfChallenges journey! This intermediate challenge presents the most efficient way to compute the n‑th Fibonacci number in Python: a linear‑time iterative loop with constant space. It avoids the exponential blow‑up of naive recursion and the memory overhead of memoization, making it suitable for very large n (e.g., 10 000).

The method is widely used in real‑world applications, competitive programming, and technical interviews when recursion or memoization is disallowed.

Fibonacci Sequence Example

F₀ = 0, F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, …

Implementation

def fibonacci(n: int) -> int:
    """Return the n‑th Fibonacci number.

    Args:
        n: A non‑negative integer.

    Raises:
        ValueError: If n is negative.
    """
    if n < 0:
        raise ValueError("n must be a non‑negative integer")

    if n == 0:
        return 0
    if n == 1:
        return 1

    # Track the two most recent numbers
    prev = 0  # F(n‑2)
    curr = 1  # F(n‑1)

    for _ in range(2, n + 1):
        next_value = prev + curr
        prev = curr
        curr = next_value

    return curr

Key Points

• Constant space – only two variables (prev, curr) are stored.
• Linear time – one pass from 2 to n.
• No recursion – eliminates stack overflow risk.
• Error handling – validates that n is non‑negative.

Usage Example

raw = input("Enter n (non‑negative integer): ").strip()

if raw == "":
    print("No input provided. Exiting.")
else:
    n = int(raw)
    result = fibonacci(n)
    print(f"Fibonacci number F{n} =", result)

Running the script with n = 10 yields:

Fibonacci number F10 = 55

The implementation scales effortlessly to huge values (e.g., n = 1000 runs instantly).

Advanced Alternatives

• Matrix exponentiation – O(log n) time.
• Binet’s closed‑form formula – uses floating‑point arithmetic with rounding.
• Generator – produces an infinite Fibonacci sequence lazily.

For the vast majority of practical scenarios, the iterative O(n) / O(1) solution is the optimal choice.

Conclusion

Day 56 delivers the fastest practical Fibonacci implementation in Python. Feel free to experiment with large inputs and share your results!