Skip to content
Data Structures & Algorithms

Fibonacci Sequence interview questions and answers

35 questions, 25 with code. About 2 h 31 min to read them all.

By TestLab · Updated

Plan for an interview
35 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

How is the Fibonacci sequence defined

The Fibonacci sequence is a sequence of integers in which each number is the sum of the two preceding numbers. Conventionally, F(0) = 0 and F(1) = 1, producing 0, 1, 1, 2, 3, 5, 8, 13, 21, ….

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition and Recurrence

  • Recurrence relation: F(n) = F(n - 1) + F(n - 2) for n ≥ 2

  • Base cases: F(0) = 0, F(1) = 1

  • Closed form (Binet’s formula): F(n) = (φⁿ - ψⁿ) / √5, where φ = (1 + √5) / 2 ≈ 1.618 and ψ = (1 - √5) / 2 ≈ -0.618

  • Binet’s formula loses precision for large n when evaluated with floating-point arithmetic and can eventually overflow. Python’s arbitrary-precision integers avoid overflow, but a floating-point implementation of the formula is still inexact.

Mathematical Properties

  • Growth rate: F(n) ≈ φⁿ / √5, so the sequence grows exponentially with base φ, the golden ratio.

  • Divisibility: For positive m ≥ 3, F(m) divides F(n) if and only if m divides n. The case m = 2 is exceptional because F(2) = 1 divides every Fibonacci number.

  • Cassini’s identity: F(n - 1) · F(n + 1) - F(n)² = (-1)ⁿ

  • Partial sum: F(0) + F(1) + … + F(n) = F(n + 2) - 1

Computational Approaches

Approach Time Complexity Space Complexity When to Use
Naive recursion O(φⁿ), approximately O(1.618ⁿ) O(n) stack Teaching only; exponential because of overlapping subproblems
Memoization (top-down DP) O(n) O(n) cache plus O(n) stack When recursion is natural and the recursion depth is safe
Iterative (bottom-up DP) O(n) O(1) Simple general-purpose solution when linear time is sufficient
Fast doubling or matrix exponentiation O(log n) O(log n) stack recursively or O(1) iteratively Large indices requiring logarithmically many arithmetic operations

Why fast doubling is O(log n): It uses the identities
F(2k) = F(k) · [2 · F(k + 1) - F(k)]
F(2k + 1) = F(k + 1)² + F(k)²
to halve the index at each step, analogous to exponentiation by squaring.

Complexity Details

  • Naive recursion: Time is O(φⁿ) because the recursive call tree grows exponentially. Space is O(n) for the recursion stack.

  • Memoization: Each F(i) is computed once, giving O(n) time and O(n) total auxiliary space for the cache and recursion stack.

  • Iterative: One loop and two stored Fibonacci values give O(n) time and O(1) auxiliary space.

  • Fast doubling: The recursion depth is O(log n), so time is O(log n) and recursive stack space is O(log n); an iterative version uses O(1) auxiliary space.

All space figures exclude the input integer and include recursive call stacks. These time and space bounds use the standard unit-cost arithmetic model; with arbitrary-precision integers, runtime and memory also depend on the resulting integers’ Θ(n) bit lengths.

Integer Size Considerations

  • Python 3’s int has arbitrary precision, so Fibonacci values do not overflow, subject to available memory.

  • A signed 64-bit integer has a maximum of 9,223,372,036,854,775,807, and F(93) = 12,200,160,415,121,876,738 exceeds it.

  • Use an appropriate wider or arbitrary-precision type for larger values: __int128 where supported in C++, BigInteger in Java, or BigInt in JavaScript. Modular arithmetic is another option when only F(n) mod m is required.

Common Pitfalls and Interview Tips

  • Off-by-one errors: Confirm whether the problem uses F(0) = 0, F(1) = 1 or F(1) = 1, F(2) = 1.

  • Recursion depth: Python 3.12’s default recursion limit is approximately 1,000, so naive and memoized recursive implementations can fail near that depth. Prefer an iterative implementation or raise the limit cautiously.

  • Mutating input: Avoid modifying caller-owned data unless the problem explicitly requires it.

  • Memoization purpose: Fibonacci is the classic example of overlapping subproblems: naive recursion recalculates the same Fibonacci values repeatedly.

  • Follow-up questions:

  • Compute F(n) mod m using fast doubling with modular arithmetic.

  • Find the index of a given Fibonacci number using an estimate followed by verification, or binary search with a Fibonacci lookup function.

  • Sum even Fibonacci numbers using the fact that F(3k) is even.

  • Optimize O(n) dynamic-programming space to O(1) by retaining only the last two values.

2

How do you calculate the nth Fibonacci number recursively?

A recursive Fibonacci function uses the recurrence F(n) = F(n - 1) + F(n - 2). Memoization ensures that overlapping subproblems are calculated only once, reducing the standard recursive implementation from exponential time to linear time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

The Fibonacci sequence is defined as:

  • F(0) = 0

  • F(1) = 1

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

A recursive implementation directly follows this recurrence. Without memoization, calculating F(n) repeatedly evaluates the same values—for example, F(3) is needed by both F(4) and F(5).

Memoization stores each computed result in a cache. After F(k) has been evaluated, later calls for F(k) return immediately instead of repeating its recursive calls.

Approach Comparison

All space figures are auxiliary space and exclude the input integer. Because the input is one scalar, including it would not change the Big-O result. Complexities use the standard model in which an arithmetic operation costs O(1).

Approach Best time Average time Worst time Auxiliary space When to use
Naive recursion O(phi^n) O(phi^n) O(phi^n) O(n) recursion stack Teaching recursion only
Memoized recursion O(n) O(n) O(n) O(n) cache and stack Clear recursive solutions
Iterative calculation O(n) O(n) O(n) O(1) Avoid recursion-depth limits
Matrix exponentiation O(log n) O(log n) O(log n) O(1) with fixed-size matrices Very large n
Fast doubling O(log n) O(log n) O(log n) O(log n) recursion stack Large n with efficient arithmetic

The coarse bound for naive recursion is often written as O(2^n), but O(phi^n) is more precise, where phi ≈ 1.618.

Code Example

from functools import cache


@cache
def fibonacci(n: int) -> int:
    """Return F(n), where F(0) = 0 and F(1) = 1, using memoized recursion."""
    if n < 0:
        raise ValueError("n must be non-negative")

    if n <= 1:
        return n

    return fibonacci(n - 1) + fibonacci(n - 2)


print(fibonacci(10))  # 55

functools.cache is available in Python 3.9 and later. It wraps the function with a dictionary-backed cache, so each Fibonacci value is calculated at most once.

Example Walkthrough

For n = 5:

  1. F(5) requests F(4) and F(3).

  2. F(4) requests F(3) and F(2).

  3. F(3) requests F(2) and F(1).

  4. F(2) requests F(1) and F(0).

  5. The base values are returned and combined upward.

Call Result
F(0) 0
F(1) 1
F(2) 1
F(3) 2
F(4) 3
F(5) 5

The second request for F(3) is answered from the cache rather than evaluated again.

Edge Cases and Performance

  • Negative n: The function raises ValueError because the sequence is defined only for non-negative indices.

  • Base cases: n = 0 returns 0, and n = 1 returns 1.

  • Empty input: Not applicable; the function accepts one integer rather than a collection.

  • Large n: Recursive depth can approach n, so values near Python’s default recursion limit of roughly 1,000 may raise RecursionError. Use iteration or fast doubling for large indices.

  • Integer size: Python integers do not overflow. In languages with signed 64-bit integers, F(92) is the largest Fibonacci value that fits; F(93) exceeds 2^63 - 1.

  • Binet’s formula: The approximation F(n) ≈ phi^n / sqrt(5) is mathematically useful but loses floating-point precision for large n.

Common Pitfalls

  • Wrong base cases: Using F(1) = F(2) = 1 changes the requested indexing convention; this answer uses F(0) = 0.

  • No memoization: Plain recursion creates overlapping subproblems and takes O(phi^n) time.

  • Ignoring recursion depth: Memoization fixes repeated work but does not remove the call-stack requirement.

  • Using floating-point arithmetic: Closed-form approximations can produce incorrect values at large indices.

  • Typical follow-up questions: Interviewers may ask for the iterative solution, time and space complexity, handling of negative inputs, or an O(log n) fast-doubling implementation.

3

How to implement Fibonacci iteratively for the nth number in Python

The iterative approach calculates the nth Fibonacci number by tracking only the two previous values in a loop, avoiding the overhead and depth limits of recursion. It is the standard solution for interviews because it uses constant extra space while remaining easy to trace.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm relies on the definition where F(0) = 0 and F(1) = 1. Instead of calling the function repeatedly, it starts with these two base values and updates them in each step.

  1. Initialize prev to 0 and curr to 1.

  2. Loop n times. In each iteration, update prev to the old curr and curr to the sum of the old prev and curr.

  3. After the loop, prev holds the nth Fibonacci number.

This works because each new number is the sum of the two preceding ones, so keeping just the last two numbers is sufficient to compute the next one.

Complexity Analysis

  • Time Complexity: O(n). The loop runs exactly n times, performing a constant amount of work in each iteration.

  • Space Complexity: O(1). Only two integer variables are stored, regardless of the input size. This is auxiliary space; the input itself is not counted.

Comparison of Approaches

Approach Time Complexity Space Complexity When to Use
Naive Recursion O(2^n) O(n) stack Only for small n; demonstrates overlapping subproblems
Memoization O(n) O(n) When repeated queries are needed; adds recursion overhead
Iterative O(n) O(1) Best general-purpose solution for a single nth number
Matrix Exponentiation O(log n) O(1) For extremely large n; complex to implement

Note that Binet’s formula exists as a closed-form solution, but it uses floating-point arithmetic and loses precision for large n, making it unreliable for exact integer results.

Code Example

def fibonacci_iterative(n: int) -> int:
    """Return the nth Fibonacci number using an iterative approach.

    Uses F(0) = 0 and F(1) = 1.
    """
    if n < 0:
        raise ValueError("Input must be a non-negative integer.")
    prev, curr = 0, 1
    for _ in range(n):
        prev, curr = curr, prev + curr
    return prev

# Example call:
# print(fibonacci_iterative(10)) -> 55

Common Pitfalls

  • Integer Overflow: Python integers automatically handle large values, but in languages like Java or C++, the 92nd Fibonacci number exceeds a 64-bit integer. Use long or a big integer library for n > 92.

  • Off-by-One Errors: Ensure the loop runs n times, not n-1 times, which would return the (n-1)th number.

  • Recursion Limits: A recursive solution without memoization hits Python’s default recursion limit (about 1000) quickly; the iterative version avoids this entirely.

  • Negative Input: Always validate that n is non-negative, as the Fibonacci sequence is defined for natural numbers.

4

What is recursive Fibonacci’s time complexity, and how can it be optimized?

The naive recursive Fibonacci solution runs in O(φⁿ) time, where φ is the golden ratio, because it repeatedly calculates the same Fibonacci values. Caching results reduces the complexity to O(n), while fast doubling computes the result in O(log n) arithmetic operations.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Naive Recursive Complexity

Using the standard definition F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2), the direct recursion is:

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

Its call tree expands exponentially because each call creates two more calls. For example, fibonacci(4) recalculates fibonacci(2) and fibonacci(1) multiple times.

  • Time: O(φⁿ), often conservatively described as O(2ⁿ).

  • Auxiliary space: O(n) because the maximum recursion stack contains n + 1 calls.

  • Input storage: The input is not counted in auxiliary space.

  • Best, average, and worst case: All are the same for a fixed valid n.

Approaches Compared

In the standard unit-cost arithmetic model:

Approach Time Auxiliary Space When to Use
Naive recursion O(φⁿ) O(n) recursion stack Only for explaining exponential growth
Memoization O(n) O(n) cache plus stack When teaching top-down dynamic programming
Iterative calculation O(n) O(1) When simplicity and constant space matter
Matrix exponentiation O(log n) O(1) fixed-size matrices When matrix methods are the focus
Fast doubling O(log n) O(log n) recursion stack For efficient large-index calculation

Memoization improves the naive solution by caching each computed value. Fibonacci is the classic example of overlapping subproblems: naive recursion solves F(k) repeatedly, while memoization solves it once.

Fast Doubling

Fast doubling uses these identities:

  • F(2k) = F(k) × (2F(k + 1) - F(k))

  • F(2k + 1) = F(k)² + F(k + 1)²

A recursive call returns the pair (F(k), F(k + 1)). Because each call halves the index, only logarithmically many levels are needed.

For exact large integers, the time is more precisely O(log n) arithmetic operations; the bit-level cost also depends on the size of the integers being multiplied.

Code Example

def fibonacci(n: int) -> int:
    """Return F(n) using fast doubling, with F(0) = 0 and F(1) = 1."""
    if n < 0:
        raise ValueError("n must be non-negative")

    def fibonacci_pair(k: int) -> tuple[int, int]:
        """Return (F(k), F(k + 1))."""
        if k == 0:
            return 0, 1

        fib_k, fib_k_next = fibonacci_pair(k // 2)

        even = fib_k * (2 * fib_k_next - fib_k)
        odd = fib_k * fib_k + fib_k_next * fib_k_next

        if k % 2 == 0:
            return even, odd
        return odd, even + odd

    return fibonacci_pair(n)[0]


print(fibonacci(5))  # 5

The function handles n = 0 and n = 1, rejects negative indices, and does not mutate external input.

Example Walkthrough

For fibonacci(5):

Call Returned Pair
fibonacci_pair(0) (0, 1)
fibonacci_pair(1) (1, 1)
fibonacci_pair(2) (1, 2)
fibonacci_pair(5) (5, 8)

The final result is F(5) = 5.

Common Pitfalls

  • Incorrect base cases: Use F(0) = 0 and F(1) = 1; changing the starting point changes every result.

  • Floating-point formulas: Binet’s formula, (φⁿ - ψⁿ) / √5, loses precision for large n because it uses floating-point arithmetic.

  • Integer overflow: Python integers do not overflow. In signed 64-bit languages, F(92) is the last value that fits; F(93) exceeds the maximum, so wider integers or arbitrary-precision types are needed.

  • Recursion depth: Memoized recursion uses O(n) stack frames and exceeds Python’s default limit of about 1,000 frames near n = 1000; fast doubling uses only O(log n) frames.

  • Complexity assumptions: O(log n) fast doubling assumes constant-cost arithmetic; exact large-integer multiplication has additional bit-level costs.

5

How does memoization optimize Fibonacci calculations?

Memoization caches previously computed Fibonacci values so each recursive subproblem is evaluated only once. This removes the repeated calculations that make naive recursion exponential.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Using the standard definition:

  • F(0) = 0

  • F(1) = 1

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

Naive recursion repeatedly calculates the same values. For example, F(5) calculates F(3) through both F(4) and F(3).

With memoization:

  1. Check whether F(index) is already in a dictionary.

  2. If it is, return the cached result immediately.

  3. Otherwise, calculate its two smaller subproblems, store the result, and return it.

Fibonacci is the classic example of overlapping subproblems: different recursive branches request the same Fibonacci values.

Complexity Comparison

The table uses standard unit-cost arithmetic and excludes the input itself from space calculations.

Approach Time Auxiliary Space When to Use
Naive recursion O(phi^n) O(n) recursion stack Demonstrating the problem only
Top-down memoization O(n) O(n) cache plus O(n) recursion stack Recursive solution with repeated subproblems
Bottom-up iteration O(n) O(1) extra space Simple, efficient solution for most inputs
Fast doubling O(log n) O(log n) recursive stack Large indexes where logarithmic time matters
Matrix exponentiation O(log n) O(1) with iterative multiplication Very large indexes or repeated matrix queries

Memoization computes each of the n relevant Fibonacci values once. Its O(n) space includes both the memoization dictionary and the recursion stack; the input itself is not counted. These deterministic implementations have the same best, average, and worst-case bounds under standard algorithmic-analysis assumptions.

Step-by-Step Example

For F(5), the memoized recursion proceeds as follows (only the first computation of each value is shown; cache hits are omitted for brevity):

  1. calculate(5) – not in cache, calls calculate(4) and calculate(3).

  2. calculate(4) – not in cache, calls calculate(3) and calculate(2).

  3. calculate(3) – not in cache, calls calculate(2) and calculate(1).

  4. calculate(2) – not in cache, calls calculate(1) and calculate(0).

  5. calculate(1) returns 1 (base case), calculate(0) returns 0 (base case).

  6. calculate(2) computes 1, stores memo[2]=1, returns 1.

  7. calculate(3) gets calculate(1)=1 from cache, computes 2, stores memo[3]=2, returns 2.

  8. calculate(4) gets calculate(2)=1 from cache, computes 3, stores memo[4]=3, returns 3.

  9. calculate(5) gets calculate(3)=2 from cache, computes 5, stores memo[5]=5, returns 5.

After the computation, the cache contains {0:0, 1:1, 2:1, 3:2, 4:3, 5:5}. Each of the five non‑base values is calculated exactly once.

Precision and Edge Cases

  • Base cases: F(0) and F(1) must be initialized correctly.

  • Negative input: The sequence is normally defined only for nonnegative indexes, so negative values should raise an error.

  • Recursion depth: Python’s default recursion limit is about 1,000. Large indexes may require an explicit stack, a raised recursion limit, or an iterative solution.

  • Python integers: Python integers do not overflow. In languages such as Java or C++, signed 64-bit integers support Fibonacci values through approximately F(92); larger values require arbitrary-precision integers.

  • Binet’s formula: F(n) = round(phi^n / sqrt(5)) can estimate Fibonacci numbers in constant arithmetic time, but floating-point precision is lost for large n.

  • Bit-level costs: Exact runtime and storage grow with the size of the resulting integers; the standard O(n) bounds assume unit-cost arithmetic and integer storage.

Code Example

def fibonacci(n: int) -> int:
    """Return F(n) using top-down memoization, with F(0)=0 and F(1)=1."""
    if n < 0:
        raise ValueError("n must be non-negative")

    memo: dict[int, int] = {0: 0, 1: 1}

    def calculate(index: int) -> int:
        if index in memo:
            return memo[index]

        result = calculate(index - 1) + calculate(index - 2)
        memo[index] = result
        return result

    return calculate(n)


print(fibonacci(10))  # 55

Interview Tips

  • Clarify the indexing convention before coding; F(0) = 0, F(1) = 1 avoids off-by-one errors.

  • Explain why memoization reduces exponential work to O(n): each subproblem is computed once.

  • Mention that the cache and recursion stack both contribute to the O(n) space bound.

  • Be ready to convert the recursive solution to bottom-up iteration if recursion depth is a concern.

  • Common follow-up questions ask for the iterative, fast-doubling, and matrix-exponentiation solutions, including their space requirements.

6

How do you generate Fibonacci iteratively in Python?

An iterative Fibonacci generator computes each term from the previous two, avoiding the repeated calculations and recursion depth issues of naive recursion. Using the standard definition, (F(0)=0) and (F(1)=1), it generates the first n terms in O(n) time and uses O(1) auxiliary space, excluding the returned list.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

The recurrence is:

[ F(i) = F(i-1) + F(i-2) ]

Keep a list starting with [0]. If count is 1, return it. Otherwise, append 1 and then repeatedly append the sum of the last two terms until count terms are collected.

This works for n = 0, which returns an empty list, and n = 1, which returns [0].

Complexity Comparison

Approach Time Space When to use
Naive recursion O(φⁿ), commonly written O(2ⁿ) O(n) recursion stack Only for illustrating overlapping subproblems
Memoization O(n) O(n) cache plus O(n) recursion stack When many recursive calls need to share results
Iterative solution O(n) O(1) auxiliary space; O(n) including output Best default for generating a linear sequence
Matrix exponentiation O(log n) matrix operations O(1) auxiliary matrix space When calculating one very large term
Fast doubling O(log n) O(log n) recursion stack, or O(1) iteratively When calculating one very large term efficiently

For the iterative implementation, each iteration performs constant work. The algorithm therefore takes O(n) time. It stores only two Fibonacci values, giving O(1) auxiliary space. The input n occupies O(1) space, while the returned list occupies O(n) space.

Example Walkthrough

For generate_fibonacci(7):

Iteration Last two terms New term Sequence
Initial 0, 1 — [0, 1]
1 1, 1 1 [0, 1, 1]
2 1, 2 2 [0, 1, 1, 2]
3 2, 3 3 [0, 1, 1, 2, 3]
4 3, 5 5 [0, 1, 1, 2, 3, 5]
5 5, 8 8 [0, 1, 1, 2, 3, 5, 8]

Code Example

def generate_fibonacci(count: int) -> list[int]:
    """Return the first count Fibonacci numbers, starting with 0 and 1."""
    if count <= 0:
        return []

    sequence = [0]
    if count == 1:
        return sequence

    sequence.append(1)
    for _ in range(2, count):
        next_term = sequence[-1] + sequence[-2]
        sequence.append(next_term)

    return sequence


# Example: generate_fibonacci(7) returns [0, 1, 1, 2, 3, 5, 8]

Common Pitfalls

  • Wrong starting values: Use F(0) = 0 and F(1) = 1 unless the problem explicitly defines another sequence.

  • Off-by-one errors: Decide whether “first n terms” includes F(0). This implementation includes it.

  • Confusing auxiliary and total space: The iterative variables use O(1) space, but returning all n terms requires O(n) total space.

  • Integer overflow: Python integers do not overflow. In languages with fixed-width integers, signed 64-bit values become insufficient around (F(93)); use arbitrary-precision integers when larger values are required.

  • Floating-point formulas: Binet’s formula can calculate Fibonacci numbers approximately, but it loses precision for large n. Use exact integer iteration instead.

  • Recursive depth: Naive recursion creates overlapping subproblems and can reach Python’s recursion limit. Memoization reduces the work to O(n), while iteration avoids the recursion stack entirely.

7

How does dynamic programming optimize Fibonacci sequence computation?

Dynamic programming optimizes the Fibonacci sequence by storing solutions to overlapping subproblems, avoiding the exponential recomputation of naive recursion. The recurrence relation F(n) = F(n-1) + F(n-2) with base cases F(0)=0, F(1)=1 exhibits optimal substructure and overlapping subproblems, making it a textbook DP example.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Naive Recursion and Its Problem

The direct recursive implementation follows the mathematical definition but recomputes the same values repeatedly. For F(5), the call tree expands to 15 calls, with F(3) computed twice, F(2) three times, and F(1) five times. Time complexity is O(φⁿ) where φ ≈ 1.618 (the golden ratio), often loosely written as O(2ⁿ). Space complexity is O(n) due to the recursion stack depth.

Dynamic Programming Approaches

DP solves this by computing each subproblem once. Two standard patterns apply:

  • Memoization (top-down): Keep the recursive structure but cache results in a dictionary or array. Before recursing, check the cache; after computing, store the result. Time O(n), space O(n) for cache + O(n) stack.

  • Tabulation (bottom-up): Build the solution iteratively from the base cases upward. Only the two most recent values are needed, reducing space to O(1). This is the preferred production approach.

Recurrence in words: The nth Fibonacci number is the sum of the previous two numbers, starting from 0 and 1.

Trace for n = 5 (iterative): 1. Initialize prev = 0 (F(0)), curr = 1 (F(1)) 2. i = 2: prev, curr = curr, prev + curr → prev = 1 (F(1)), curr = 1 (F(2)) 3. i = 3: prev, curr = curr, prev + curr → prev = 1 (F(2)), curr = 2 (F(3)) 4. i = 4: prev, curr = curr, prev + curr → prev = 2 (F(3)), curr = 3 (F(4)) 5. i = 5: prev, curr = curr, prev + curr → prev = 3 (F(4)), curr = 5 (F(5)) 6. Return curr = 5

Comparison Table

Approach Time Space When to Use
Naive recursion O(φⁿ) O(n) stack Teaching the problem only
Memoization O(n) O(n) cache + O(n) stack Recursive logic is clearer
Iterative (bottom-up) O(n) O(1) General purpose, large n
Fast doubling / matrix exponentiation O(log n) O(log n) stack or O(1) Very large n (n > 10⁶)

Code Example

def fibonacci(n: int) -> int:
    """
    Return the nth Fibonacci number (0-indexed) using O(1) space iteration.
    F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n >= 2.
    """
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 0
    prev, curr = 0, 1  # F(0), F(1)
    for i in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr


# Example call
print(fibonacci(10))  # 55

Common Pitfalls

  • Off-by-one base cases: Forgetting that F(0)=0 and F(1)=1 leads to shifted sequences. Always verify with n=0, 1, 2.

  • Integer overflow in other languages: F(93) exceeds 64-bit signed integer range. Use arbitrary-precision integers (Python int, Java BigInteger, C++ boost::multiprecision::cpp_int).

  • Naive recursion for n > 30: Exponential time makes it unusable; always apply memoization or iteration.

  • Binet’s formula precision loss: The closed form F(n) = (φⁿ - ψⁿ)/√5 uses floating point and loses exactness around n > 70 in double precision. Avoid for exact integer results.

  • Negative n handling: The standard definition is for n ≥ 0. If negative indices are needed, define the extension explicitly (F(-n) = (-1)ⁿ⁺¹F(n)).

Interview Tips

  • Follow-up: “Compute F(n) mod m.” Use the iterative method with % m at each step; Pisano period can reduce n for very large values.

  • Follow-up: “What if n is 10¹⁸?” Switch to fast doubling (O(log n)) or matrix exponentiation. The recurrence for fast doubling:

  • F(2k) = F(k)[2F(k+1) - F(k)]

  • F(2k+1) = F(k+1)² + F(k)²

  • Space optimization: Explicitly mention reducing O(n) array to O(1) variables — interviewers look for this.

  • Memoization vs. tabulation: Know when each shines. Memoization is easier when the recursion tree is sparse; tabulation is faster and avoids stack limits.

8

How to compute nth Fibonacci number with matrix exponentiation and complexity

The matrix exponentiation method computes the nth Fibonacci number in logarithmic time by raising a transformation matrix to the power of n.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Comparison of Approaches

Approach Time Space Notes
Naive recursion O(2^n) O(n) Exponential, redundant work
Memoization O(n) O(n) Top-down DP
Iterative O(n) O(1) Bottom-up DP
Matrix exponentiation O(log n) O(1) Fastest for very large n

How It Works

The recurrence F(n) = F(n-1) + F(n-2) maps to the matrix equation: [[1, 1], [1, 0]]^n * [[1], [0]] = [[F(n+1)], [F(n)]]

We compute the matrix power using binary exponentiation (square and multiply), which requires O(log n) matrix multiplications. The recursive version uses O(log n) stack space, while the iterative version uses O(1).

  • Binet’s formula: F(n) = (phi^n - psi^n) / sqrt(5). It is O(1) but loses precision with floats for large n.

  • Walkthrough (n=5):

  • Binary of 5 is 101.

  • M^1 = [[1, 1], [1, 0]].

  • M^2 = [[2, 1], [1, 1]].

  • M^4 = M^2 * M^2 = [[5, 3], [3, 2]].

  • M^5 = M^4 * M = [[8, 5], [5, 3]].

  • M^5[0][1] = 5, so F(5) = 5.

Code Example

def fibonacci_matrix(n: int) -> int:
    """
    Compute the nth Fibonacci number using matrix exponentiation.
    Uses F(0) = 0 and F(1) = 1.
    Time complexity: O(log n). Space complexity: O(1).
    """
    if n < 0:
        raise ValueError("Input must be non-negative")
    if n == 0:
        return 0
    if n == 1:
        return 1

    def multiply(first: list[list[int]], second: list[list[int]]) -> list[list[int]]:
        return [
            [first[0][0] * second[0][0] + first[0][1] * second[1][0],
             first[0][0] * second[0][1] + first[0][1] * second[1][1]],
            [first[1][0] * second[0][0] + first[1][1] * second[1][0],
             first[1][0] * second[0][1] + first[1][1] * second[1][1]]
        ]

    base_matrix = [[1, 1], [1, 0]]
    result_matrix = [[1, 0], [0, 1]]  # Identity matrix
    exponent = n

    while exponent > 0:
        if exponent % 2 == 1:
            result_matrix = multiply(result_matrix, base_matrix)
        base_matrix = multiply(base_matrix, base_matrix)
        exponent //= 2

    return result_matrix[0][1]

# Example call: fibonacci_matrix(5) -> 5

Common Pitfalls

  • Integer overflow: Python ints do not overflow, but C++ or Java need long long or BigInteger beyond n = 92.

  • Off-by-one errors: Ensure the matrix power matches the index n, not n-1.

  • Base cases: The loop already returns F(0) = 0 and F(1) = 1 correctly; the explicit checks only make the intent clear.

  • Negative input: Always validate n is non-negative.

9

How can the nth Fibonacci number be computed using the golden ratio?

Binet’s formula can compute the nth Fibonacci number using the golden ratio. For (F(0)=0) and (F(1)=1), the formula is rounded to the nearest integer, although high-precision arithmetic is needed for large values.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Formula and Method

The golden ratio and its conjugate are:

[ phi=frac{1+sqrt{5}}{2}, qquad psi=frac{1-sqrt{5}}{2} ]

Binet’s formula is:

[ F_n=frac{phi^n-psi^n}{sqrt{5}} ]

Because (|psi|<1), its contribution becomes insignificant for large (n). Therefore:

[ F_n=operatorname{round}left(frac{phi^n}{sqrt{5}}right) ]

Equivalently:

[ F_n=leftlfloorfrac{phi^n}{sqrt{5}}+frac{1}{2}rightrfloor ]

Python’s built-in float eventually loses integer precision because it stores only about 53 bits of significant precision. The implementation below uses Decimal, with precision based on the size of the result.

Complexity Comparison

Approach Time Auxiliary space When to use
Naive recursion (O(phi^n)), more precisely (O(1.618^n)) (O(n)) recursion stack Demonstrating overlapping subproblems
Memoized recursion (O(n)) (O(n)) cache plus (O(n)) stack Avoiding repeated calculations
Iterative recurrence (O(n)) (O(1)) Simple, exact implementation
Matrix exponentiation or fast doubling (O(log n)) (O(1)) iteratively or (O(log n)) recursively Exact, efficient computation
Golden-ratio calculation (O(log n)) high-precision multiplications (O(n)) bits of working precision Explaining Binet’s formula or estimating large indices

The golden-ratio approach performs exponentiation by squaring, requiring (O(log n)) multiplications of numbers containing (O(n)) bits. If multiplying (k)-bit numbers costs (M(k)), its bit-time is (O(M(n)log n)).

All cases have the same complexity because these algorithms are deterministic. Space figures exclude the scalar input and returned integer but include the recursion stack. The returned Fibonacci integer itself requires (Theta(n)) bits.

Code Example

from decimal import Decimal, ROUND_HALF_EVEN, localcontext


def fibonacci_golden_ratio(n: int) -> int:
    """Return F(n) using Binet's formula with high-precision arithmetic."""
    if n < 0:
        raise ValueError("n must be non-negative")

    # log10(phi) is approximately 0.20898764024997873.
    # Add guard digits for rounding and accumulated arithmetic error.
    precision_digits = max(
        50,
        (n * 20898764024997873) // 100_000_000_000_000_000 + 30,
    )

    with localcontext() as context:
        context.prec = precision_digits

        sqrt_five = Decimal(5).sqrt()
        phi = (Decimal(1) + sqrt_five) / 2

        # Calculate phi**n using exponentiation by squaring.
        result = Decimal(1)
        base = phi
        exponent = n

        while exponent > 0:
            if exponent % 2 == 1:
                result *= base
            exponent //= 2
            if exponent > 0:
                base *= base

        estimate = result / sqrt_five
        return int(estimate.to_integral_value(rounding=ROUND_HALF_EVEN))


print(fibonacci_golden_ratio(10))  # 55

Worked Example

For (n=5):

  1. Compute (phi=(1+sqrt{5})/2approx1.618034).

  2. Calculate (phi^5approx11.090170).

  3. Divide by (sqrt{5}): (11.090170/2.236068approx4.959898).

  4. Round to the nearest integer: (F_5=5).

Accuracy and Edge Cases

  • Empty or invalid input: Fibonacci has no empty sequence interpretation; the function rejects negative indices with ValueError.

  • One element: n=0 returns 0, and n=1 returns 1.

  • Large indices: Use enough decimal precision; ordinary floating-point formulas become unreliable around (F(79)), which exceeds exact double precision.

  • Integer size: Python integers do not overflow. In languages with signed 64-bit integers, (F(92)) is the last value that fits; use arbitrary-precision integers beyond that.

  • Exact production use: Fast doubling is generally preferable because it returns an exact integer without approximating irrational numbers.

Common Pitfalls

  • Using round(phi**n / sqrt(5)) with float for large n.

  • Mixing the conventions (F(0)=0,F(1)=1) and (F(1)=1,F(2)=1).

  • Assuming Binet’s formula is exact without accounting for the conjugate term.

  • Claiming constant space despite storing a result containing (Theta(n)) bits.

  • Forgetting that negative Fibonacci indices are not part of the standard sequence.

10

How can precomputed Fibonacci values answer multiple nth queries efficiently?

Precompute Fibonacci values up to the largest requested index, then answer each query with direct list access. Using F(0) = 0 and F(1) = 1, the recurrence is F(n) = F(n-1) + F(n-2). Precomputation takes O(N) time, each query takes O(1) time, and the table occupies O(N) space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Estimate the maximum index N needed by all queries.

  2. Create an array where index n stores F(n).

  3. Set the base cases to F(0) = 0 and F(1) = 1.

  4. Compute each remaining value once using the recurrence.

  5. Answer future queries with a direct lookup such as fibonacci[n].

This avoids repeatedly calculating overlapping subproblems, the defining inefficiency of naive recursive Fibonacci implementations.

Complexity Comparison

Approach Time Space When to use
Naive recursion O(phi^n) O(n) recursion stack Only for explaining the exponential problem
Memoization O(n) O(n) cache and recursion stack Recomputing or selectively caching values
Iterative precomputation O(n) O(1) auxiliary space Producing values sequentially
Precomputed lookup table O(N) preprocessing, O(1) per query O(N) including the table Many queries with known maximum index
Matrix exponentiation or fast doubling O(log n) O(log n) recursive stack or O(1) iterative space A small number of very large-index queries

The table’s O(N) space includes the precomputed output but not the input itself. Its auxiliary space beyond that output is O(1).

Small Walkthrough

For a maximum index of 5:

Index n F(n)
0 0
1 1
2 1
3 2
4 3
5 5

After computing these entries once, queries for F(3) and F(5) are constant-time list accesses.

Code Example

def precompute_fibonacci(max_n: int) -> list[int]:
    """Return Fibonacci values from F(0) through F(max_n), inclusive."""
    if max_n < 0:
        raise ValueError("max_n must be non-negative")

    values = [0] * (max_n + 1)

    if max_n >= 1:
        values[1] = 1

    for n in range(2, max_n + 1):
        values[n] = values[n - 1] + values[n - 2]

    return values


fibonacci = precompute_fibonacci(10)
print(fibonacci)     # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
print(fibonacci[10]) # 55

Alternatives and Best Practices

  • Binet’s formula estimates F(n) directly as
    ((phi^n - psi^n) / sqrt(5)), where phi = (1 + sqrt(5)) / 2. It is useful mathematically, but floating-point calculations lose precision for large n.

  • Choose based on query count: precompute when many moderate-size queries are expected; use fast doubling when only a few extremely large indices are queried.

  • Handle empty ranges: max_n = 0 should return [0].

  • Validate negative indices: Fibonacci numbers are conventionally defined only for non-negative indices.

  • Avoid unnecessary storage: if only a few scattered queries exist, memoization or fast doubling may use less memory.

  • Consider integer limits: Python integers do not overflow. In languages with fixed-width signed 64-bit integers, F(93) already exceeds the maximum value, so use 64-bit integers only through F(92) or a big-integer type beyond that.

Common Pitfalls

  • Using F(1) = 1 and F(2) = 1 without also supporting F(0) = 0.

  • Returning F(max_n) instead of a zero-indexed table containing every value through F(max_n).

  • Assuming each query remains O(1) if the table must be rebuilt for every request.

  • Building an enormous table when the requested index is large but the number of queries is small.

  • Using a recursive implementation that approaches Python’s recursion limit; iterative precomputation avoids this issue.

11

How can a Fibonacci sequence use two arbitrary starting values?

A generalized Fibonacci sequence keeps the usual addition rule but replaces the standard starting values with any two integers. If its first two terms are (x_0) and (x_1), subsequent terms follow (x_n = x{n-1} + x{n-2}).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition and Recurrence

For arbitrary initial values (x_0) and (x_1):

[ x_n = x{n-1} + x{n-2}, qquad n ge 2 ]

The standard Fibonacci sequence is the special case (F(0)=0), (F(1)=1). Another example is (3,5,8,13,21,ldots).

Generalized terms can also be related to standard Fibonacci numbers:

[ x_n = F_{n-1}x_0 + F_nx_1, qquad n ge 1 ]

This relationship makes fast doubling and matrix exponentiation possible.

Binet’s formula for standard Fibonacci numbers is:

[ F_n = frac{phi^n-psi^n}{sqrt{5}} ]

where (phi=(1+sqrt5)/2) and (psi=(1-sqrt5)/2). It should not be used to compute large terms with floating-point numbers because it loses precision and can eventually produce incorrect integers.

Approach Comparison

The following complexities assume constant-time arithmetic and exclude the input values themselves.

Approach Time: best = average = worst Space When to use
Naive recursion (O(phi^n)), commonly approximated as (O(2^n)) (O(n)) recursion stack Teaching only; it repeats identical subproblems
Memoization (O(n)) (O(n)) cache plus (O(n)) recursion stack Demonstrating overlapping subproblems
Iterative generation (O(n)) (O(1)) auxiliary; (O(n)) if all terms are stored Normal implementation and sequence generation
Fast doubling or matrix exponentiation (O(log n)) for one selected term (O(log n)) recursive stack, or (O(1)) with iterative matrix operations Computing a very distant term efficiently

Memoization is the classic Fibonacci example of overlapping subproblems: naive recursion repeatedly calculates the same preceding terms. Iterative generation avoids both repeated work and Python’s approximately 1,000-frame recursion-depth limit.

Code Example

The function below generates the requested number of terms using two arbitrary integer starting values.

from collections.abc import Iterator


def generalized_fibonacci(first: int, second: int, count: int) -> Iterator[int]:
    """Yield count terms of a Fibonacci-like sequence with arbitrary starts."""
    if count <= 0:
        return

    yield first
    if count == 1:
        return

    yield second
    for term_index in range(2, count):
        first, second = second, first + second
        yield second


print(list(generalized_fibonacci(3, 5, 7)))
# [3, 5, 8, 13, 21, 34, 55]

For first = 3 and second = 5, the states are:

Step Previous pair New term
1 (3, 5) 3
2 (3, 5) 5
3 (5, 8) 8
4 (8, 13) 13
5 (13, 21) 21
6 (21, 34) 34
7 (34, 55) 55

Common Pitfalls and Interview Tips

  • Off-by-one errors: The first two values are already provided, so only count - 2 additional terms require calculation.

  • Empty or short requests: This implementation returns no terms when count <= 0 and only first when count == 1.

  • Duplicate or negative starting values: Both are valid and require no special handling.

  • Integer overflow: Python integers do not overflow. In languages with fixed-width integers, standard Fibonacci exceeds the signed 64-bit range at (F(93)); arbitrary starting values may overflow even earlier.

  • Space accounting: The generator uses (O(1)) auxiliary space, with no recursion stack, excluding the input. A caller that converts it to a list incurs (O(n)) output space.

  • Large indices: If only one distant term is needed, mention the identity (x_n=F_{n-1}x_0+F_nx_1) and fast doubling or matrix exponentiation.

12

How can I sum the first n Fibonacci numbers efficiently?

Use the identity (sum_{i=0}^{n-1} F(i)=F(n+1)-1), then calculate (F(n+1)) with fast doubling in (O(log n)) arithmetic steps without generating the entire sequence.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Using the standard definitions (F(0)=0), (F(1)=1), and (F(n)=F(n-1)+F(n-2)), the first (n) terms are (F(0)) through (F(n-1)).

Fast doubling uses these identities:

[ F(2k)=F(k)bigl(2F(k+1)-F(k)bigr) ]

[ F(2k+1)=F(k)^2+F(k+1)^2 ]

The algorithm processes the bits of (n+1), maintaining a pair ((F(k),F(k+1))). Each bit either doubles the index or doubles it and adds one, requiring only (O(log n)) arithmetic steps.

For example, when (n=5):

  1. The terms are (F(0),F(1),F(2),F(3),F(4)): 0, 1, 1, 2, 3.

  2. Their sum is 7.

  3. Fast doubling computes (F(6)=8).

  4. The identity gives (F(6)-1=7).

If “first (n)” instead means (F(1)) through (F(n)), the corresponding identity is:

[ sum_{i=1}^{n}F(i)=F(n+2)-1 ]

Approach Comparison

Approach Time Space When to use
Naive recursion (O(2^n)) upper bound; more precisely (O(phi^n)) (O(n)) recursion stack Only for explaining repeated computation
Memoization (O(n)) (O(n)) Teaches overlapping subproblems and reuse of cached Fibonacci values
Sequential iteration (O(n)) (O(1)) auxiliary variables Simple when (n) is small
Matrix exponentiation (O(log n)) (O(1)) auxiliary variables General matrix-based solution
Fast doubling (O(log n)) (O(1)) auxiliary integer variables Preferred for computing a large Fibonacci number efficiently

Memoization addresses the classic problem of overlapping subproblems, where naive recursion repeatedly calculates the same values.

Binet’s formula provides a mathematical closed form:

[ F(n)=operatorname{round}left(frac{phi^n}{sqrt{5}}right) ]

However, floating-point calculations lose precision for large (n), so it is unsuitable when an exact integer is required.

Complexity

  • Time: (O(log n)) in the best, average and worst cases under the standard unit-cost arithmetic model.

  • Space: (O(1)) auxiliary integer variables, excluding the input and the returned integer. There is no recursion stack because the implementation is iterative.

  • Integer storage: Python’s arbitrary-precision integers require (O(n)) bits for the result, so actual memory usage is larger than a constant number of machine words.

Code Example

def sum_first_fibonacci(n: int) -> int:
    """Return F(0) + F(1) + ... + F(n - 1) for a nonnegative n."""
    if n < 0:
        raise ValueError("n must be nonnegative")

    target = n + 1
    fib_k, fib_k_plus_one = 0, 1

    for bit_index in range(target.bit_length() - 1, -1, -1):
        # Fast-doubling identities for F(2k) and F(2k + 1).
        fib_2k = fib_k * (2 * fib_k_plus_one - fib_k)
        fib_2k_plus_one = fib_k * fib_k + fib_k_plus_one * fib_k_plus_one

        if (target >> bit_index) & 1:
            fib_k = fib_2k_plus_one
            fib_k_plus_one = fib_2k + fib_2k_plus_one
        else:
            fib_k = fib_2k
            fib_k_plus_one = fib_2k_plus_one

    return fib_k - 1


print(sum_first_fibonacci(5))  # 7

Common Pitfalls

  • Off-by-one errors: This implementation sums (F(0)) through (F(n-1)), not (F(1)) through (F(n)).

  • Empty input: n = 0 returns 0, the sum of no terms.

  • One element: n = 1 returns 0, because the only included term is (F(0)).

  • Negative input: n < 0 raises ValueError.

  • Duplicate values: Fibonacci values such as the two occurrences of 1 are counted normally.

  • Floating-point calculations: Avoid Binet’s formula when exact results are needed for large (n).

  • Integer overflow: Python integers do not overflow. Other languages need arbitrary-precision integers around (F(93)), before sums containing roughly 92 terms exceed a signed 64-bit integer.

  • Irrelevant cases: Sorted input, disconnected graphs and cycles do not apply to this sequence algorithm.

13

How is the Lucas sequence defined and generated in Python?

The Lucas sequence is an integer sequence defined by the same recurrence as the Fibonacci sequence but with different initial values. It begins 2, 1, 3, 4, 7, 11, 18, 29, ... and is useful for studying recurrence relations, dynamic programming, and the relationship between Fibonacci and Lucas numbers.

Read full answer

Applies toPython 3.12

Definition and Properties

The Lucas sequence is defined as:

  • L(0) = 2

  • L(1) = 1

  • L(n) = L(n - 1) + L(n - 2) for n >= 2

For example:

  • L(2) = L(1) + L(0) = 1 + 2 = 3

  • L(3) = L(2) + L(1) = 3 + 1 = 4

  • L(4) = L(3) + L(2) = 4 + 3 = 7

For n >= 1, the sequence is related to Fibonacci numbers by:

L(n) = F(n - 1) + F(n + 1)

where Fibonacci numbers use the standard definition F(0) = 0, F(1) = 1.

The closed-form expression is:

L(n) = phi^n + psi^n

where phi = (1 + sqrt(5)) / 2 and psi = (1 - sqrt(5)) / 2.

Binet’s formula can similarly calculate Fibonacci numbers, but both formulas lose precision when floating-point arithmetic is used for large n. Integer-based iteration avoids that issue.

Approach Comparison

The recurrence has the same complexity characteristics as the equivalent Fibonacci algorithms. All deterministic bounds below are the best, average, and worst cases for valid inputs.

Approach Time Space When to use
Naive recursion O(phi^n), commonly approximated as O(2^n) O(n) recursion stack Demonstrate overlapping subproblems only
Memoization O(n) O(n) cache plus recursion stack Avoid repeated recursive work; Fibonacci is the classic example of overlapping subproblems
Iterative generation O(n) O(1) auxiliary space; O(n) for the returned list Best choice for generating the sequence
Matrix exponentiation or fast doubling O(log n) for one indexed term O(log n) with recursion or O(1) iteratively Calculate a very large-indexed term

Space figures include the recursion stack when recursion is used. The input is a single integer and is therefore treated as O(1); the returned list is counted separately.

Step-by-Step Example

For count = 6, the iterative algorithm maintains the two most recent terms:

Iteration Previous Current New value Result
Initialization — — — [2]
Initialize 2 1 — [2, 1]
index = 2 2 1 3 [2, 1, 3]
index = 3 1 3 4 [2, 1, 3, 4]
index = 4 3 4 7 [2, 1, 3, 4, 7]
index = 5 4 7 11 [2, 1, 3, 4, 7, 11]

Code Example

def generate_lucas(count: int) -> list[int]:
    """Return the first count Lucas numbers using L(0)=2 and L(1)=1."""
    if count < 0:
        raise ValueError("count must be non-negative")

    if count == 0:
        return []

    if count == 1:
        return [2]

    previous, current = 2, 1
    sequence = [previous, current]

    for index in range(2, count):
        next_value = previous + current
        sequence.append(next_value)
        previous, current = current, next_value

    return sequence


print(generate_lucas(8))  # [2, 1, 3, 4, 7, 11, 18, 29]

The function handles an empty result when count is 0, returns only L(0) when count is 1, and produces the first two terms when count is 2. Negative counts are rejected because a sequence cannot contain a negative number of elements.

Common Pitfalls

  • Wrong initial values: Lucas numbers start with 2, 1, not 0, 1.

  • Off-by-one errors: Decide explicitly whether the input means the number of terms or the highest index.

  • Incorrect complexity claims: The iterative algorithm uses O(n) time because it performs one constant-time addition per term.

  • Floating-point formulas: Binet’s formula can produce inaccurate results for large indices; use integer arithmetic for exact results.

  • Integer limits: Python integers do not overflow. In languages such as Java or C++, values beyond the Fibonacci index around 92 can exceed a signed 64-bit integer, so a big-integer type may be required.

  • Recursion depth: A recursive implementation should use memoization or an explicit stack for large inputs because Python’s default recursion limit is approximately 1,000.

14

How is Fibonacci used to count 2×n rectangle tilings?

Fibonacci counting solves the tiling problem through the recurrence T(n) = T(n - 1) + T(n - 2), which gives T(n) = F(n + 1) when F(0) = 0 and F(1) = 1. This assumes the standard 2×1 tiles may be rotated.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Fibonacci Applies

Consider the leftmost uncovered part of a 2×n rectangle:

  • Vertical tile: One 2×1 tile fills the first column, leaving a 2×(n - 1) rectangle. This contributes T(n - 1) arrangements.

  • Horizontal tiles: Two 1×2 tiles must be placed together to fill the first two columns, leaving a 2×(n - 2) rectangle. This contributes T(n - 2) arrangements.

Therefore:

T(n) = T(n - 1) + T(n - 2)
T(0) = 1
T(1) = 1

The base case T(0) = 1 represents one way to tile an empty board: use no tiles. This is the Fibonacci sequence shifted by one position:

T(n) = F(n + 1)

Naive recursive Fibonacci is the classic example of overlapping subproblems, because it repeatedly calculates the same smaller Fibonacci values.

Approach Comparison

Approach Time Auxiliary Space When to Use
Naive recursion O(phi^n), also bounded by O(2^n) O(n) recursion stack Demonstrate the recurrence only
Memoization O(n) O(n) dictionary or array Simple, readable solution
Iterative dynamic programming O(n) O(1) Ordinary board sizes
Fast doubling O(log n) O(log n) recursion stack Large n with clear code requirements
Matrix exponentiation O(log n) O(1) with scalar iterative variables Large n when matrix operations are preferred

Here, phi ≈ 1.618. These bounds assume constant-time arithmetic; Fibonacci numbers have increasingly large bit representations.

Worked Example

For a 2×4 board:

Width Calculation Tiling Count
0 Base case 1
1 T(1) = 1 1
2 T(1) + T(0) = 1 + 1 2
3 T(2) + T(1) = 2 + 1 3
4 T(3) + T(2) = 3 + 2 5

Thus, T(4) = F(5) = 5.

Complexity and Edge Cases

  • Empty board: n = 0 returns 1.

  • One column: n = 1 returns 1, using one vertical tile.

  • Negative width: Rejected with ValueError.

  • Recursion depth: Fast doubling has depth O(log n), far below Python’s default limit of about 1000 for practical inputs.

  • Space accounting: Auxiliary space is O(log n) for the recursion stack; the scalar input n is not counted.

  • Integer size: Python integers do not overflow. In signed 64-bit languages, the tiling count first exceeds the range at n = 92, where F(93) is larger than 2^63 - 1; use arbitrary-precision integers when necessary.

  • Binet’s formula: The mathematical formula F(n) = (phi^n - psi^n) / sqrt(5) exists, but floating-point evaluation loses precision for large n and should not be used for exact counting.

Code Example

def count_tilings(width: int) -> int:
    """Count tilings of a 2 x width board using rotatable 2 x 1 tiles."""
    if width < 0:
        raise ValueError("width must be non-negative")

    def fibonacci_pair(index: int) -> tuple[int, int]:
        """Return (F(index), F(index + 1)) using fast doubling."""
        if index == 0:
            return 0, 1

        previous_half, current_half = fibonacci_pair(index // 2)
        even_value = previous_half * (2 * current_half - previous_half)
        odd_value = previous_half * previous_half + current_half * current_half

        if index % 2 == 0:
            return even_value, odd_value
        return odd_value, even_value + odd_value

    return fibonacci_pair(width + 1)[0]


print(count_tilings(4))  # 5

Fast doubling uses the identities F(2k) = F(k) * (2F(k + 1) - F(k)) and F(2k + 1) = F(k)^2 + F(k + 1)^2.

Common Pitfalls

  • Off-by-one error: The tiling count is F(n + 1), not F(n).

  • Incorrect empty-board base case: Use T(0) = 1, not 0.

  • Counting horizontal tiles individually: Two horizontal tiles must be paired when covering the first two columns.

  • Assuming arbitrary precision: Check the integer range in the target language before using fixed-width integers.

  • Typical follow-up questions: Interviewers may ask for memoization, an iterative O(n) implementation, fast doubling, or clarification about whether tile rotation is allowed.

15

How can you calculate large Fibonacci numbers without integer overflow?

Use fast doubling to calculate a Fibonacci number in (O(log n)) arithmetic steps and store it in an arbitrary-precision integer. Python integers do not overflow; fixed-width languages require 64-bit integers only up to (F(92)), then a big-integer type such as BigInteger.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Using (F(0)=0) and (F(1)=1), fast doubling relies on these identities:

[ F(2k)=F(k)times(2F(k+1)-F(k)) ]

[ F(2k+1)=F(k)^2+F(k+1)^2 ]

Maintain the pair ((F(k), F(k+1))) while processing the binary digits of n. Each digit changes the current index from (k) to either (2k) or (2k+1), so only (O(log n)) doubling steps are required.

Approach Comparison

Approach Time Space When to use
Naive recursion (O(phi^n)), often simplified to (O(2^n)) (O(n)) recursion stack Teaching recursion only
Memoization (O(n)) (O(n)) cached values Demonstrating overlapping subproblems
Bottom-up iteration (O(n)) (O(1)) integer variables Moderate n and simpler code
Matrix exponentiation (O(log n)) (O(1)) matrices Matrix-based algorithm practice
Fast doubling (O(log n)) arithmetic steps (O(1)) integer variables Large n with efficient arithmetic

These time bounds assume unit-cost arithmetic. With arbitrary-precision integers, actual runtime also depends on the cost of multiplying numbers containing (O(n)) bits.

Example Walkthrough

For n = 5, its binary representation is 101:

  1. Start with ((F(0),F(1))=(0,1)).

  2. Read 1: obtain ((F(1),F(2))=(1,1)).

  3. Read 0: obtain ((F(2),F(3))=(2,3)).

  4. Read 1: obtain ((F(5),F(8))=(5,8)).

  5. Return the first value, 5.

Code Example

def fibonacci(n: int) -> int:
    """Return F(n) using iterative fast doubling, where F(0) = 0."""
    if isinstance(n, bool) or not isinstance(n, int):
        raise TypeError("n must be an integer")
    if n < 0:
        raise ValueError("n must be non-negative")

    # Current pair is (F(k), F(k + 1)).
    current, following = 0, 1

    for bit_position in range(n.bit_length() - 1, -1, -1):
        doubled = current * (2 * following - current)
        adjacent = current * current + following * following

        if (n >> bit_position) & 1:
            current, following = adjacent, doubled + adjacent
        else:
            current, following = doubled, adjacent

    return current


print(fibonacci(100))  # 354224848179261915075

Complexity and Edge Cases

  • Time: (O(log n)) arithmetic operations because each binary digit of n is processed once.

  • Auxiliary space: (O(1)) big-integer variables, with no recursion stack. In bit terms, temporary integers require (O(n)) bits.

  • Output space: The returned integer contains (O(n)) bits. The input occupies (O(log n)) bits and is not mutated.

  • Edge cases: fibonacci(0) returns 0, fibonacci(1) returns 1, and negative indices raise ValueError.

In Python, integers have arbitrary precision and never overflow. In a signed 64-bit language, (F(92)) still fits, but (F(93)=12,200,160,415,121,876,738) exceeds the maximum signed 64-bit value of (9,223,372,036,854,775,807). Use a big-integer type from that point onward.

Common Pitfalls

  • Incorrect base cases: Define (F(0)=0) and (F(1)=1), not (F(1)=0).

  • Floating-point formulas: Binet’s formula, (F(n)approx phi^n/sqrt{5}), loses precision for large n because it uses floating-point arithmetic.

  • Fixed-width arithmetic: A signed 64-bit integer overflows beginning at (F(93)); check the language’s integer limits before choosing a type.

  • Printing enormous integers: Python 3.12 limits decimal integer conversion by default. For trusted workloads requiring very large output, adjust sys.set_int_max_str_digits appropriately.

  • Complexity wording: Say (O(log n)) arithmetic steps rather than claiming every big-integer multiplication takes constant time.

  • Likely follow-up: Interviewers may ask you to derive the fast-doubling identities, explain why naive recursion repeats work, or compare fast doubling with matrix exponentiation.

16

How do you implement the nth Fibonacci number modulo m?

Fast doubling computes the nth Fibonacci number modulo m in O(log n) time by using identities for F(2k) and F(2k + 1). The implementation uses F(0) = 0 and F(1) = 1, and maintains the pair (F(k), F(k + 1)) modulo m while processing the bits of n.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

Fast doubling uses these identities:

  • F(2k) = F(k) * (2 * F(k + 1) - F(k))

  • F(2k + 1) = F(k)^2 + F(k + 1)^2

The algorithm processes the binary representation of n from most significant bit to least significant bit. If the current pair represents (F(k), F(k + 1)), the next bit determines whether the new prefix is 2k or 2k + 1.

The function below uses an iterative implementation, so it avoids recursion-stack growth. It performs every arithmetic operation modulo m.

Complexity and Alternatives

All deterministic approaches have the same best, average, and worst-case time complexity.

Approach Time Auxiliary space Reason
Naive recursion O(φ^n) O(n) The recursion tree repeatedly recomputes overlapping subproblems; φ is approximately 1.618.
Top-down memoization O(n) O(n) Each Fibonacci value is computed once; the memo table and recursion stack require O(n) space.
Bottom-up iteration O(n) O(1) A rolling pair computes each value once.
Matrix exponentiation O(log n) O(1) Binary exponentiation applies the Fibonacci transition matrix O(log n) times.
Iterative fast doubling O(log n) O(1) Each binary digit of n requires constant work.
Recursive fast doubling O(log n) O(log n) The recursion depth follows the number of bits in n.

Space figures exclude the input itself but include any recursion stack. The iterative fast-doubling implementation uses O(1) auxiliary space and has no recursion stack.

Binet’s formula, F(n) = (φ^n - ψ^n) / √5, is useful for explaining the mathematical growth of the sequence, but floating-point calculations lose precision for large n. It should not be used for exact modular Fibonacci computation.

Code Example

def fibonacci_mod(n: int, m: int) -> int:
    """Return the nth Fibonacci number modulo m, using fast doubling."""
    if n < 0:
        raise ValueError("n must be non-negative")
    if m <= 0:
        raise ValueError("m must be a positive integer")

    # Maintain (F(prefix), F(prefix + 1)) modulo m.
    current, following = 0, 1 % m

    for bit_index in range(n.bit_length() - 1, -1, -1):
        even = (current * (2 * following - current)) % m
        odd = (current * current + following * following) % m

        if (n >> bit_index) & 1:
            current, following = odd, (even + odd) % m
        else:
            current, following = even, odd

    return current


if __name__ == "__main__":
    print(fibonacci_mod(10, 100))  # 55

For n = 10, the binary representation is 1010. The maintained pairs are:

Processed bit Binary prefix (F(prefix), F(prefix + 1)) mod 100
1 1 (1, 1)
0 2 (1, 2)
1 5 (5, 8)
0 10 (55, 89)

Therefore, the function returns 55.

Edge Cases and Practical Notes

  • n = 0: Returns 0.

  • n = 1: Returns 1 % m.

  • m = 1: Every result modulo 1 is 0.

  • Negative n or non-positive m: The function raises ValueError.

  • Large n: The running time depends on the number of bits in n, not on the numeric size of n.

  • Python integers: They do not overflow. In languages such as Java or C++, computing exact Fibonacci values beyond n = 92 requires 64-bit limits to be checked or a big-integer type to be used. Modular arithmetic keeps intermediate values bounded by m, although multiplication still requires a type wide enough for the product.

Common Pitfalls

  • Using the wrong initial convention, such as F(1) = F(2) = 1, without stating the indexing clearly.

  • Forgetting to reduce the initial following value modulo m when m = 1.

  • Applying fast doubling to F(2k + 1) but forgetting that the new pair must be (F(2k + 1), F(2k + 2)).

  • Using floating-point Binet’s formula for large indices.

  • Assuming the recursive implementation has constant space; its recursion stack is O(log n).

  • Using O(n) time when an interview specifically asks for an efficient logarithmic-time solution.

17

How to compute the last k digits of the nth Fibonacci number

Fast doubling computes the requested digits in O(log n) modular arithmetic operations. It applies the Fibonacci recurrence F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1, while retaining each intermediate result modulo 10^k.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The last k decimal digits of F(n) are:

F(n) mod 10^k

Fast doubling maintains the pair (F(m), F(m+1)) while processing the binary digits of n. Given:

  • a = F(m)

  • b = F(m+1)

the following identities produce the next pair:

  • F(2m) = a × (2b - a)

  • F(2m+1) = a² + b²

For each binary digit of n:

  • A 0 selects the pair (F(2m), F(2m+1)).

  • A 1 selects (F(2m+1), F(2m+2)), where F(2m+2) = F(2m) + F(2m+1).

All calculations are reduced modulo 10^k, so the algorithm never needs to construct the complete Fibonacci number.

Approach Comparison

The following complexities assume constant-time modular arithmetic:

Approach Time Auxiliary Space When to Use
Naive recursion O(2^n) upper bound; tight O(phi^n) O(n) recursion stack Demonstrates overlapping subproblems
Memoization O(n) O(n) cache Reuses previously computed values
Iterative recurrence O(n) O(1) Simple implementation for moderate n
Matrix exponentiation O(log n) O(1) scalar state Alternative for very large n
Fast doubling O(log n) O(1) iterative state Efficient and direct; used below

Memoization is the classic Fibonacci example of overlapping subproblems, because naive recursion repeatedly calculates the same values.

Code Example

def last_k_digits(n: int, k: int) -> str:
    """Return the last k decimal digits of F(n), preserving leading zeros."""
    if n < 0:
        raise ValueError("n must be non-negative")
    if k < 0:
        raise ValueError("k must be non-negative")
    if k == 0:
        return ""

    modulus = 10 ** k
    fib, next_fib = 0, 1

    # Process n from its most significant binary bit to its least.
    for bit_position in range(n.bit_length() - 1, -1, -1):
        even = (fib * (2 * next_fib - fib)) % modulus
        odd = (fib * fib + next_fib * next_fib) % modulus

        if (n >> bit_position) & 1:
            fib, next_fib = odd, (even + odd) % modulus
        else:
            fib, next_fib = even, odd

    return f"{fib:0{k}d}"


print(last_k_digits(10, 5))  # Expected output: 00055

Example Walkthrough

For n = 10, the binary representation is 1010. Using modulus 100000:

Processed Bit Index m (F(m), F(m+1))
Initial 0 (0, 1)
1 1 (1, 1)
0 2 (1, 2)
1 5 (5, 8)
0 10 (55, 89)

Therefore, the last five digits of F(10) = 55 are returned as "00055".

Complexity and Edge Cases

  • Time: O(log n) modular arithmetic steps because each binary digit of n is processed once. The bit-level cost also depends on the size and multiplication cost of the k-digit modular values.

  • Auxiliary space: O(1) big-integer variables under the unit-cost arithmetic model, with no recursion stack. Counting actual big-integer storage, it is O(k) bits; including the input and output, O(k + log n) bits.

  • Recursive alternative: Recursive fast doubling uses O(log n) recursion-stack space. The iterative version avoids recursion-depth limits.

  • Edge cases:

  • n = 0 returns the zero-padded representation of F(0) = 0.

  • n = 1 returns the zero-padded representation of F(1) = 1.

  • k = 0 returns an empty string.

  • Negative n or k raises ValueError.

  • When k exceeds the number of digits in F(n), leading zeros are preserved.

Common Pitfalls

  • Using F(1) = 1, F(2) = 1 without also stating F(0) = 0 can cause an off-by-one error.

  • The modulus must be 10^k, not 10 * k.

  • Returning an integer discards leading zeros; return a string when formatting matters.

  • Binet’s formula can lose floating-point precision for large n, so it is unsuitable for exact digits.

  • Python integers do not overflow. In Java or C++, a signed 64-bit integer exceeds the range around F(93); use arbitrary-precision integers or overflow-safe modular multiplication.

  • Interviewers commonly follow up with: “Why do the fast-doubling identities work?”, “How would memoization compare?”, or “What changes when k is very large?”

18

How do I check whether a number is Fibonacci?

A nonnegative integer is a Fibonacci number exactly when one of 5n² + 4 or 5n² - 4 is a perfect square. This perfect-square criterion allows exact validation using math.isqrt, without floating-point rounding.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Fibonacci Definition

The standard Fibonacci sequence is:

  • F(0) = 0

  • F(1) = 1

  • F(k) = F(k - 1) + F(k - 2) for k >= 2

Its first values are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ....

The perfect-square theorem states that a nonnegative integer n belongs to this sequence if and only if 5n² + 4 or 5n² - 4 is a perfect square.

Approach Comparison

All complexities below exclude the input itself. For deterministic algorithms, best, average, and worst cases are the same.

Approach Time Auxiliary space When to use
Naive recursive generation O(phi^n), often described as O(2^n) O(n) recursion stack Demonstrating exponential recomputation
Memoized recursion O(n) O(n) cache plus O(n) stack Teaching memoization
Iterative sequence generation O(n) O(1) Simple, practical implementations
Matrix exponentiation or fast doubling O(log n) O(1) iterative; O(log n) recursive stack Computing a distant Fibonacci number efficiently
Perfect-square criterion O(1) in the fixed-width model O(1) Checking membership directly

Memoization is effective because naive Fibonacci recursion repeatedly calculates the same values, such as F(2), creating overlapping subproblems.

Fast doubling uses these identities:

  • F(2k) = F(k) × (2F(k + 1) - F(k))

  • F(2k + 1) = F(k)² + F(k + 1)²

Example Walkthrough

For number = 13:

  1. Calculate 5 × 13² = 845.

  2. Test 845 + 4 = 849: it lies between 29² = 841 and 30² = 900, so it is not a square.

  3. Test 845 - 4 = 841: this equals 29², so it is a perfect square.

  4. Return True. Indeed, 13 = F(7).

Complexity and Edge Cases

  • Fixed-width arithmetic model: time is O(1) because the algorithm performs a constant number of arithmetic and square-root operations. Auxiliary space is O(1).

  • Arbitrary-precision Python integers: let B = O(log n) be the input’s bit length. Multiplication and integer square root have costs dependent on B; a conservative schoolbook-arithmetic bound is O(B³) time and O(B) bits of auxiliary space.

  • Negative numbers: return False; Fibonacci numbers are nonnegative.

  • Zero: return True, because F(0) = 0.

  • One: return True, because F(1) = 1.

  • The function does not mutate its input.

Code Example

from math import isqrt


def is_fibonacci(number: int) -> bool:
    """Return whether number is a Fibonacci number."""
    if number < 0:
        return False

    scaled = 5 * number * number

    plus_four = scaled + 4
    root = isqrt(plus_four)
    if root * root == plus_four:
        return True

    minus_four = scaled - 4
    if minus_four < 0:
        return False

    root = isqrt(minus_four)
    return root * root == minus_four


print(is_fibonacci(13))  # True

isqrt returns the integer square root, so root * root == value is an exact perfect-square test.

Common Pitfalls

  • Off-by-one errors: use F(0) = 0 and F(1) = 1 unless the problem explicitly defines another convention.

  • Floating-point validation: Binet’s formula, F(n) = round(phi^n / sqrt(5)), loses precision for large n in floating-point arithmetic. Use integer arithmetic for reliable membership checks.

  • Integer overflow: Python integers do not overflow. In signed 64-bit languages, F(92) is the last value that fits; F(93) exceeds the maximum.

  • Negative square-root input: never pass a negative value to isqrt; guard it first as shown above.

  • Common follow-up questions: generate the first n terms, compute F(n) using fast doubling, find the largest Fibonacci number not exceeding a limit, or calculate Fibonacci numbers modulo a value.

19

How to implement fast doubling for the nth Fibonacci number?

The fast doubling algorithm computes the nth Fibonacci number in O(log n) arithmetic steps. It derives F(2k) and F(2k+1) from F(k) and F(k+1), using F(0) = 0 and F(1) = 1.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Fast doubling uses these identities:

  • F(2k) = F(k) * (2 * F(k+1) - F(k))

  • F(2k+1) = F(k)^2 + F(k+1)^2

Let P(n) = (F(n), F(n+1)). First recursively obtain P(k) where k = n // 2, then calculate:

  • c = F(2k)

  • d = F(2k+1)

The result is (c, d) when n is even and (d, c + d) when n is odd. The base case is P(0) = (0, 1).

Trace for n = 5: 1. The recursive chain is P(5) -> P(2) -> P(1) -> P(0). 2. P(0) = (0, 1). 3. The odd case gives P(1) = (1, 1), and the even case gives P(2) = (1, 2). 4. For k = 2, c = 1 * (2 * 2 - 1) = 3 and d = 1² + 2² = 5. 5. Since 5 is odd, P(5) = (d, c + d) = (5, 8).

Approach Comparison

Approach Time Auxiliary space Notes
Naive recursion O(2^n); more precisely O(phi^n) O(n) Exponential because calls overlap and repeat.
Memoization O(n) O(n) Fibonacci’s repeated recursive calls are the classic overlapping-subproblems example.
Linear iteration O(n) O(1) Simple but performs linearly many arithmetic steps.
Matrix exponentiation O(log n) O(1) iterative or O(log n) recursive Exponentiates a Fibonacci transition matrix.
Fast doubling O(log n) O(log n) recursive or O(1) iterative Combines two Fibonacci identities directly.

Complexity

These bounds use the standard unit-cost arithmetic model. Auxiliary space excludes the input and returned output.

  • Time: Best, average, and worst case are all O(log n) because the algorithm is deterministic and halves the index at every level.

  • Space: Recursive fast doubling uses O(log n) auxiliary space because the recursion stack contains O(log n) frames. An iterative bit-scanning version uses O(1) stored values.

  • Integer cost: Python integers do not overflow, but arbitrary-precision multiplication is not constant-time. The returned F(n) has Theta(n) bits, so O(log n) is an arithmetic-step bound rather than a bit-time bound.

Binet’s formula uses only a constant number of formula terms, but treating the power calculation as O(1) is an idealization. Direct floating-point evaluation loses exact precision for large indices, commonly around n = 70 with double precision.

Code Example

def fast_doubling_fibonacci(n: int) -> int:
    """Return F(n) for a non-negative integer n using fast doubling."""
    if n < 0:
        raise ValueError("n must be non-negative")

    def _fib_pair(k: int) -> tuple[int, int]:
        # Base case: F(0) = 0 and F(1) = 1
        if k == 0:
            return 0, 1

        # Compute the pair for the smaller index.
        f_k, f_k_plus_1 = _fib_pair(k // 2)

        # Apply the fast-doubling identities.
        f_2k = f_k * (2 * f_k_plus_1 - f_k)
        f_2k_plus_1 = f_k * f_k + f_k_plus_1 * f_k_plus_1

        if k % 2 == 0:
            return f_2k, f_2k_plus_1
        return f_2k_plus_1, f_2k + f_2k_plus_1

    return _fib_pair(n)[0]


print(fast_doubling_fibonacci(10))  # Output: 55

Common Pitfalls

  • Boundary cases: n = 0 returns 0, n = 1 returns 1, and negative indices raise ValueError.

  • Off-by-one errors: Preserve the pair convention P(n) = (F(n), F(n+1)) and return (0, 1) only for n = 0.

  • Integer overflow: Python integers are arbitrary precision. On common 64-bit platforms, signed integers overflow at F(93) and unsigned integers overflow at F(94). Use arbitrary-precision integers, such as Python’s int or Java’s BigInteger, when necessary.

  • Recursion depth: The recursive version requires O(log n) frames. Python’s default recursion limit is about 1000; for indices needing more frames, use an iterative bit-scanning implementation or deliberately raise the limit after checking stack safety.

20

How does the Fibonacci sequence benefit Fibonacci heaps?

Fibonacci numbers provide the rank–size invariant that makes Fibonacci-heap operations efficient. They bound how large a tree can be for a given node degree, supporting the amortized analysis of consolidation and cascading cuts.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why the Fibonacci Sequence Matters

Using F(0) = 0 and F(1) = 1, a Fibonacci heap maintains the following property:

  • A node of rank k, where rank means its current number of children, has a subtree containing at least F(k + 2) nodes.

  • Fibonacci numbers grow exponentially, so a heap containing n nodes can have maximum degree only O(log n).

  • This degree bound underlies the potential-function analysis used to prove the amortized costs of operations such as extract_min and decrease_key.

The sequence does not compute heap keys. Its role is to connect node degree with a minimum subtree size.

A small step-by-step example is:

  1. A rank-0 tree needs at least one node: F(2) = 1.

  2. Linking two rank-0 roots creates a rank-1 parent with at least two nodes: F(3) = 2.

  3. Extending this argument gives the general lower bound F(k + 2) for a rank-k tree.

Operational Consequences

Fibonacci heaps consist of a heap-ordered forest and maintain a pointer to the minimum node.

  • insert adds a singleton tree to the root list without consolidating it.

  • meld concatenates two root lists and updates the minimum pointer.

  • extract_min removes the minimum, promotes its children to roots, and consolidates roots of equal degree.

  • decrease_key cuts a node when heap order is violated and may trigger cascading cuts.

Operation Best Average over an operation sequence Worst
find_min O(1) O(1) O(1)
insert O(1) O(1) O(1)
meld O(1) O(1) O(1)
decrease_key O(1) O(1) amortized O(n)
extract_min O(1) O(log n) amortized O(n)

The decrease_key worst case can be linear because cascading cuts may traverse a long ancestor path. Its amortized cost is constant because those cuts are charged to earlier structural changes.

The heap stores O(n) nodes, including the input elements. A conventional implementation can use O(log n) auxiliary space for its degree table during consolidation, excluding the stored heap.

Comparing Fibonacci Computations

The sequence itself can be computed in several ways:

Approach Time Auxiliary space When to use
Naive recursion O(2^n) upper bound (O(phi^n) more precisely) O(n) recursion stack Demonstrates exponential repeated work
Memoization O(n) O(n) cache plus O(n) stack Reuses overlapping subproblems
Iteration O(n) O(1) Best simple implementation
Matrix exponentiation or fast doubling O(log n) arithmetic operations O(log n) recursive stack or O(1) iterative Very large n

Memoization is the classic example of overlapping subproblems, where computing Fibonacci numbers repeatedly solves the same recursive subproblems. Binet’s formula is another closed form, but floating-point calculations lose precision for large n.

Python integers do not overflow. In fixed-width languages, signed 64-bit integers can represent F(92) but not F(93), so larger indices require arbitrary-precision integers.

Common Pitfalls

  • Do not confuse rank or degree with the Fibonacci sequence index: rank is the node’s number of children.

  • Do not claim that Fibonacci-heap trees have logarithmic height. Only the maximum degree is guaranteed to be O(log n); the height can be linear.

  • Do not confuse an amortized bound with a worst-case bound. In particular, decrease_key is O(1) amortized but can take O(n) in the worst case.

  • Consolidation links roots of equal degree; linking arbitrary trees would invalidate the standard analysis.

  • Avoid Binet’s formula when exact large Fibonacci values are required because floating-point rounding introduces errors.

21

How can you implement Fibonacci generation with array storage?

Use bottom-up dynamic programming with an array to store previously computed Fibonacci numbers. Each new value is calculated from the preceding two values, avoiding the repeated work performed by naive recursion.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Using the standard definition:

  • F(0) = 0

  • F(1) = 1

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

The array holds the generated sequence from F(0) through F(n). After initializing the base cases, the algorithm fills each remaining position once.

Fibonacci is the classic example of overlapping subproblems: naive recursion repeatedly calculates the same values, while memoization or bottom-up storage calculates each value only once.

Approach Comparison

Approach Time Space When to Use
Naive recursion O(2^n) (more precisely O(phi^n)) O(n) recursion stack Illustrating exponential repeated work
Top-down memoization O(n) O(n) memo array plus O(n) recursion stack Reusing cached results across queries
Iterative, constant-space O(n) O(1) auxiliary space When only the latest two terms are needed
Bottom-up array O(n) O(n) array and O(1) extra space Generating or storing the complete sequence
Matrix exponentiation / fast doubling O(log n) O(log n) recursive stack, or O(1) iterative extra space Calculating one very large term efficiently

When the entire sequence must be stored, bottom-up array storage is appropriate and takes O(n) time. Fast doubling is asymptotically faster for calculating a single term, but it does not materialize every preceding term.

Binet’s formula can also estimate F(n), but floating-point calculations lose precision for large n.

Trace Example

For n = 5, the stored array changes as follows:

Index Value Calculation
0 0 Base case
1 1 Base case
2 1 1 + 0
3 2 1 + 1
4 3 2 + 1
5 5 3 + 2

The result is [0, 1, 1, 2, 3, 5].

Complexity and Edge Cases

  • Time: O(n) for best, average, and worst cases because each array position is computed once.

  • Space: O(n) including the returned array; auxiliary space is O(1) beyond that array.

  • Recursion stack: O(1) for the iterative implementation because it does not recurse.

  • Input accounting: The input is one integer, so it occupies O(1) space and does not change the overall bound.

  • n = 0: Returns [0].

  • n = 1: Returns [0, 1].

  • Negative n: Raises ValueError because no valid Fibonacci index is negative.

  • Large n: Python integers do not overflow. Signed 64-bit integers in other languages generally support values through F(92); use arbitrary-precision integers for larger results.

These bounds use the standard unit-cost arithmetic model. Python integer operations become more expensive as the number of bits grows.

Code Example

def generate_fibonacci(max_index: int) -> list[int]:
    """Return the Fibonacci sequence from F(0) through F(max_index), inclusive."""
    if not isinstance(max_index, int) or isinstance(max_index, bool):
        raise TypeError("max_index must be an integer")
    if max_index < 0:
        raise ValueError("max_index must be non-negative")

    if max_index == 0:
        return [0]

    fibonacci = [0] * (max_index + 1)
    fibonacci[1] = 1

    for index in range(2, max_index + 1):
        fibonacci[index] = fibonacci[index - 1] + fibonacci[index - 2]

    return fibonacci


print(generate_fibonacci(5))  # [0, 1, 1, 2, 3, 5]

Common Pitfalls

  • Off-by-one errors: Decide explicitly whether n is the final index or the number of terms. This implementation returns n + 1 terms because it includes F(0).

  • Wrong base cases: The sequence must begin with 0, 1, not 1, 1.

  • Recursion depth: Recursive solutions can approach Python’s default recursion limit for large inputs; the iterative version avoids this.

  • Integer overflow: Python is safe, but many other languages require 64-bit or arbitrary-precision integers.

  • Input mutation: The function creates and returns a new list and does not modify caller-owned data.

  • Common follow-up: Interviewers may ask for O(log n) fast doubling, memoization across multiple calls, or why naive recursion is exponential.

22

When is a Fibonacci queue preferable to a traditional FIFO queue?

A Fibonacci queue is preferable when traffic needs several weighted service tiers while avoiding the abrupt prioritization of a strict-priority queue and the head-of-line delays of FIFO. The term is not standardized; here, it means a weighted fair scheduler whose class weights are derived from Fibonacci numbers, rather than a queue implemented with a Fibonacci heap.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Using F(0) = 0 and F(1) = 1, one illustrative convention assigns service classes reciprocal Fibonacci weights:

Class Illustrative weight
Latency-sensitive traffic 1/F(2) = 1
Interactive media 1/F(3) = 1/2
Background transfer 1/F(4) = 1/3
Lowest-priority traffic 1/F(5) = 1/5

Under weighted fair scheduling, backlogged flows receive long-run bandwidth shares proportional to their positive weights. A scheduler commonly maintains a virtual finish time for each flow and serves the flow with the smallest value. Exact definitions of “Fibonacci queue” and its weight convention should therefore be confirmed before using the term in an interview.

Practical Example

Consider a router carrying VoIP calls, HD video, and software updates:

  • VoIP is sensitive to delay.

  • HD video needs sustained bandwidth.

  • Updates can tolerate delay.

FIFO serves packets in arrival order, so a burst of update packets can create head-of-line delay for voice traffic. Strict priority protects voice traffic but can starve updates.

With illustrative weights 1, 1/2, and 1/3, the normalized bandwidth shares are:

Flow Relative weight Approximate share
VoIP 1 54.5%
HD video 1/2 27.3%
Updates 1/3 18.2%

When all classes remain backlogged, latency-sensitive traffic receives preferential service without completely starving background traffic.

When to Prefer It

  • Multiple service tiers: It provides more differentiation than equal-weight fair queueing.

  • Avoided starvation: Positive weights let lower-priority flows continue receiving service under a properly implemented weighted-fair scheduler.

  • Controlled latency: Delay-sensitive traffic receives a larger share than bulk traffic.

  • Gradual degradation: Traffic can move among several levels instead of switching abruptly between normal and strict priority.

  • Simpler alternative cases: Use FIFO when per-packet arrival order is the requirement, strict priority when latency dominates, or equal-weight weighted fair queueing when equal per-flow service is sufficient.

Policy Best suited for Main drawback
FIFO Packets must be served in arrival order Large packets or bursts cause head-of-line delay
Strict priority Urgent traffic must precede everything else Lower priorities may starve
Equal-weight fair queueing Equal bandwidth per active flow No service differentiation
Fibonacci-weighted fair queueing Differentiated service with gradual tiers More configuration and scheduling overhead

Complexity

The Fibonacci weighting policy does not itself determine the container complexity.

Implementation Time Space
FIFO queue using linked nodes O(1) best, average, and worst for enqueue and dequeue because pointer updates are constant-time O(q) total including queued items; O(1) auxiliary space, with no recursion stack
Weighted scheduler using a min-heap Enqueue is O(1) best and O(log q) average and worst because an item may sift upward; minimum inspection is O(1); removal is O(log q) average and worst O(q) total including queued items and metadata; no recursion stack

If Fibonacci weights are computed at runtime:

Fibonacci method Time Auxiliary space and reason
Naive recursion O(2^n) coarse bound; more precisely O(phi^n) because recursive branches grow at the golden ratio O(n) for the recursion stack
Memoization O(n) because each Fibonacci index is computed once O(n) for the cache; Fibonacci is a classic example of overlapping recursive subproblems
Iteration O(n) because it processes indices once O(1) using two previous values
Fast doubling or matrix exponentiation O(log n) because each step halves the problem O(log n) with recursion or O(1) extra variables with an iterative implementation, under the usual unit-cost arithmetic model

Binet’s formula, F(n) = (phi^n - psi^n) / sqrt(5), has a constant number of formula terms but loses floating-point precision for large n and may produce an incorrect rounded integer. Python integers do not overflow; signed 64-bit integers in other languages overflow at F(93), so wider or arbitrary-precision integers are required beyond that point.

Common Pitfalls

  • Confirm what “Fibonacci queue” means; this answer uses it for weighted fair scheduling, not a Fibonacci heap.

  • Do not use F(0) = 0 as a service weight because a zero-weight flow cannot receive service.

  • Remember that F(1) = F(2) = 1; define how duplicate values are handled when creating tiers.

  • Weighted shares appear only when the relevant flows remain backlogged; an idle flow does not reserve unused bandwidth.

  • Distinguish FIFO’s per-packet ordering from weighted fair queueing’s per-flow bandwidth allocation.

  • Be ready to explain why FIFO, strict priority, and weighted fair queueing are each more appropriate in different scenarios.

23

How does the Pisano period affect Fibonacci numbers modulo m?

The Pisano period is the length of the repeating cycle of Fibonacci numbers computed modulo (m). Once the period (T) is known, any Fibonacci index can be reduced using (F_n bmod m = F_{n bmod T} bmod m), which is useful for repeated modular calculations.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition

The Fibonacci sequence is defined by:

[ F_0 = 0,qquad F_1 = 1,qquad F_n = F{n-1} + F{n-2}. ]

For a positive integer (m), the Pisano period (pi(m)) is the smallest positive integer (T) such that:

[ F_{n+T} equiv F_n pmod m ]

for every (n ge 0).

Equivalently, the pair of consecutive residues returns to its initial state:

[ (F_T, F_{T+1}) equiv (0,1) pmod m. ]

Examples:

  • (pi(2) = 3), because the residues are 0, 1, 1, 0, 1, 1, ....

  • (pi(5) = 20).

  • (pi(10) = 60).

  • For (m=1), every Fibonacci number is 0, so the period is 1.

Why the Period Exists

Consider the pair of consecutive Fibonacci residues:

[ (F_n, F_{n+1}) pmod m. ]

There are only (m^2) possible pairs. Each transition is:

[ (a,b) rightarrow (b, a+b) pmod m. ]

This transition is reversible: the previous pair can be recovered as:

[ (b-a,a) pmod m. ]

Therefore, the sequence of pairs is a cycle rather than an infinite non-repeating path. Since the initial pair eventually returns to (0, 1), the Pisano period always exists for positive (m).

To find it directly, generate Fibonacci residues and stop when (0, 1) first reappears. Once the period is known, reduce the index:

[ F_n bmod m = F_{n bmod pi(m)} bmod m. ]

Small Walkthrough

For (m=5), the first Fibonacci residues are:

Index (n) 0 1 2 3 4 5 6 7 8 9
(F_n bmod 5) 0 1 1 2 3 0 3 3 1 4

The complete cycle has length 20. Therefore:

[ F{100} bmod 5 = F{100 bmod 20} bmod 5 = F_0 bmod 5 = 0. ]

Approach Comparison

For deterministic Fibonacci algorithms, there is no meaningful best/average-case distinction; the listed bounds are typical and worst-case bounds.

Approach Time complexity Extra space, excluding input Notes
Naive recursion (O(phi^n)), often loosely described as (O(2^n)) (O(n)) Repeatedly recomputes overlapping subproblems; recursion stack contributes (O(n)).
Memoization (O(n)) (O(n)) Stores previously computed Fibonacci values in a cache.
Iterative calculation (O(n)) (O(1)) Keeps only the previous two values.
Matrix exponentiation or fast doubling (O(log n)) (O(1)) iteratively; (O(log n)) with recursion Best general-purpose approach for one large index.
Pisano-period detection (O(pi(m))) (O(1)) Detects the repeated residue pair; (pi(m)) is at most (O(m^2)) from the number of possible states.

With a known Pisano period, an index can first be reduced modulo the period and then evaluated using fast doubling in (O(log n)) time and (O(1)) auxiliary space.

Common Pitfalls

  • Off-by-one errors: Use (F_0=0) and (F_1=1). The initial pair is (0, 1), not (1, 1).

  • Modulus validation: Require (m>0). Handle (m=1) separately because 1 % 1 is 0.

  • Floating-point imprecision: Binet’s formula uses irrational powers and loses precision for large (n); it should not be used for exact modular results.

  • Integer overflow: Python integers do not overflow. In signed 64-bit languages, (F_{93}) and later values may overflow; use a wider or arbitrary-precision integer type.

  • Period calculation cost: Finding (pi(m)) can take (O(pi(m))) time, so for a single query, direct fast doubling may be preferable.

24

How does the Euclidean algorithm relate to Fibonacci numbers?

The Euclidean algorithm has a special worst-case relationship with Fibonacci numbers: consecutive Fibonacci numbers produce a long chain of remainder calculations, and Lamé’s theorem connects the chain length to the Fibonacci index.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Fibonacci Numbers Appear

Using F(0) = 0 and F(1) = 1, the recurrence is:

F(n + 1) = F(n) + F(n - 1)

The Euclidean algorithm repeatedly replaces (a, b) with (b, a mod b). For consecutive Fibonacci numbers:

F(n + 1) mod F(n) = F(n - 1)

Therefore, the input (F(n + 1), F(n)) reduces through consecutive Fibonacci pairs:

  1. (F(n + 1), F(n)) becomes (F(n), F(n - 1)).

  2. It becomes (F(n - 1), F(n - 2)).

  3. The process continues until the remainder reaches zero.

For example, with F(6) = 8 and F(5) = 5:

Step Euclidean input Remainder
1 (8, 5) 3
2 (5, 3) 2
3 (3, 2) 1
4 (2, 1) 0

The result is gcd(8, 5) = 1. In general, (F(n + 1), F(n)) requires n - 1 modulo divisions for n >= 2.

This is the basis of Lamé’s theorem: among pairs whose larger member is at most F(n + 1), the consecutive pair (F(n + 1), F(n)) attains the maximum division count. Because F(n) grows exponentially as approximately φ^n, where φ = (1 + √5) / 2, the number of divisions grows logarithmically in the numerical size of the input.

Fibonacci Computation Approaches

Fibonacci is the classic example of overlapping subproblems: naive recursion repeatedly recomputes the same Fibonacci values, while memoization stores each result.

Approach Time Auxiliary space Reason
Naive recursion O(2^n) upper bound; more precisely O(φ^n) O(n) It repeats recursive subproblems; the space is the recursion stack.
Memoization O(n) O(n) It computes each Fibonacci value once and caches it; the stack and cache are included.
Iterative calculation O(n) O(1) It keeps only the two latest values.
Fast doubling O(log n) O(log n) Each recursive call halves the index; the space is the recursion stack.
Matrix exponentiation O(log n) O(1) It repeatedly squares a fixed-size matrix; storage is measured in matrix entries.

Input storage is excluded from all space bounds, while applicable recursion stacks are included. These deterministic bounds have the same best, average, and worst-case asymptotic costs because the requested index determines the work. A recursive memoized or fast-doubling implementation can exceed Python’s default recursion limit for large indices; an iterative formulation avoids that issue.

Binet’s formula is:

F(n) = (φ^n - ψ^n) / √5, where ψ = (1 - √5) / 2

The common approximation F(n) ≈ φ^n / √5 loses precision with floating-point values for large n because the result grows exponentially and the correction term eventually falls below the representable precision.

Complexity and Edge Cases

Let N be the larger numerical input:

  • Best-case time: O(1) modulo operations when one operand is zero or the smaller operand divides the larger one.

  • Average-case time: O(log N) over a common model of uniformly random pairs bounded by N.

  • Worst-case time: O(log N) modulo operations, with consecutive Fibonacci inputs forming the canonical worst-case family.

  • Auxiliary space: O(1) integer variables in the standard arithmetic model, excluding the inputs.

These bounds count arithmetic operations. With arbitrary-precision integers, each modulo operation also depends on the operands’ bit lengths.

Relevant edge cases include:

  • gcd(0, 0) has no positive greatest common divisor; implementations may reject it or define a convention.

  • gcd(0, x) equals abs(x).

  • Negative inputs are handled by taking their absolute values.

  • Equal inputs have their common value as the GCD.

  • The Fibonacci base cases are F(0) = 0 and F(1) = 1.

Common Pitfalls

  • Off-by-one errors arise from different step-counting conventions; the example counts the final division that produces remainder zero.

  • Lamé’s theorem concerns the number of divisions, not the exact wall-clock cost of each arithmetic operation.

  • Do not confuse F(0) = 0, F(1) = 1 with the alternative convention F(1) = 1, F(2) = 1.

  • Python integers do not overflow. Signed 64-bit integers in other languages accommodate values only through approximately F(92); larger values require arbitrary-precision integers.

  • If implementing the algorithm, avoid mutating caller-owned input unless mutation is intentional.

  • Interviewers commonly ask why Fibonacci inputs are worst-case, why Euclid’s algorithm terminates, and how to count its divisions correctly.

25

Prove sum of first n Fibonacci numbers equals F(n+2) - 1

Proof by induction establishes that the sum of the first n Fibonacci numbers is F(n + 2) - 1, where F(0) = 0, F(1) = 1, and the sum is ∑_{i=1}^{n} F(i). The same identity also follows from a telescoping sum.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Proof by Induction

Let S(n) = ∑_{i=1}^{n} F(i), with S(0) = 0 representing the empty sum.

  1. Base case, n = 0:

S(0) = 0

F(0 + 2) - 1 = F(2) - 1 = 1 - 1 = 0

Therefore, the identity holds for n = 0.

  1. Base case, n = 1:

S(1) = F(1) = 1

F(1 + 2) - 1 = F(3) - 1 = 2 - 1 = 1

Therefore, the identity also holds for n = 1.

  1. Inductive hypothesis:

Assume that for some k ≥ 0,

S(k) = F(k + 2) - 1.

  1. Inductive step:

S(k + 1) = S(k) + F(k + 1)

= (F(k + 2) - 1) + F(k + 1)

= F(k + 2) + F(k + 1) - 1

= F(k + 3) - 1

The last equality uses the Fibonacci recurrence F(k + 3) = F(k + 2) + F(k + 1).

Thus, by induction,

∑_{i=1}^{n} F(i) = F(n + 2) - 1

for every integer n ≥ 0.

Telesoping Explanation

The Fibonacci recurrence implies

F(i) = F(i + 2) - F(i + 1).

Summing from i = 1 through n gives

F(1) + F(2) + ... + F(n)

= (F(3) - F(2)) + (F(4) - F(3)) + ... + (F(n + 2) - F(n + 1)).

All intermediate terms cancel, leaving

F(n + 2) - F(2) = F(n + 2) - 1.

Complexity Comparison

The following are conventional arithmetic-operation bounds. Auxiliary space includes memoization tables and recursion stacks but excludes the input itself. In actual bit complexity, Fibonacci-sized integers occupy Θ(n) bits, so Python’s big-integer operations are not constant-time.

Approach Time Auxiliary space When to use
Naive recursion O(2^n); more precisely O(phi^n) O(n) recursion stack Illustrating overlapping recursive calls
Memoization O(n) O(n) for memo table and stack Avoiding repeated subproblems
Iterative summation O(n) O(1) Simple implementation and moderate n
Identity with fast doubling O(log n) O(log n) recursion stack Large n with simple recursive code
Identity with iterative matrix exponentiation O(log n) O(1) auxiliary scalars Large n without recursion

These approaches are deterministic, so their best, average, and worst-case asymptotic bounds coincide.

Common Pitfalls

  • Off-by-one indexing: ∑_{i=1}^{n} F(i) = F(n + 2) - 1. If “first n” means F(0) through F(n - 1), the result is F(n + 1) - 1.

  • Negative n: The identity is defined for n ≥ 0; negative values should be rejected.

  • Integer overflow: A signed 64-bit integer holds values through F(92), but F(93) overflows. Python integers do not overflow; other languages may require arbitrary-precision integers.

  • Recursion depth: Naive recursion has Θ(n) stack depth and can exceed Python’s roughly 1000-call limit. Fast doubling has only logarithmic depth, while iterative matrix exponentiation avoids recursion entirely.

  • Floating-point formulas: Binet’s formula, F(n) = (phi^n - psi^n) / sqrt(5), loses precision with floating-point arithmetic for large n.

Interview Tips

  • Be ready to prove the identity using either induction or telescoping differences.

  • A common follow-up asks for an efficient way to calculate the sum; use the identity with fast doubling or matrix exponentiation for O(log n) arithmetic operations.

  • Explain why naive recursion is inefficient: calls such as fib(n - 1) and fib(n - 2) repeatedly calculate the same overlapping subproblems, which memoization eliminates.

  • Mention Binet’s formula when discussing closed forms, but emphasize its floating-point precision limitations.

26

How can Fibonacci numbers optimize a search algorithm?

Fibonacci search uses Fibonacci numbers to divide a sorted collection into progressively smaller sections, reducing the number of comparisons to logarithmic time. It is useful when searching an array with a fixed comparison cost, particularly in environments where simple index arithmetic is preferable to computing a binary midpoint.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Fibonacci Search Works

The Fibonacci sequence is defined by F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2).

Fibonacci search first finds the smallest Fibonacci number covering the array length. It then probes an index determined by the current Fibonacci number:

  • If the target is smaller than the probed value, it searches the left section and decreases the Fibonacci index by one.

  • If the target is larger, it searches the right section, advances the left boundary, and decreases the index by two.

  • If the values match, it returns the index.

This creates uneven partitions whose sizes follow the Fibonacci recurrence, while each iteration discards a substantial part of the remaining search space.

Example Walkthrough

For [2, 5, 8, 13, 21] and target 13:

Step Fibonacci index Left boundary Probed index Value Action
1 5 0 2 8 Target is larger, so search right
2 3 3 3 13 Return index 3

Complexity

  • Best case: O(1) when the target is found at the first probe.

  • Average case: O(log n) for a uniformly distributed successful search.

  • Worst case: O(log n), because the Fibonacci index decreases by one or two per iteration.

  • Auxiliary space: O(log n) for the stored Fibonacci numbers; the input is not counted. The values can be generated on demand to reduce this to O(1).

Search approach Time Extra space When to use
Linear search O(n) O(1) Small or unsorted collections
Binary search O(log n) O(1) General-purpose sorted-array search
Fibonacci search O(log n) O(log n) here; O(1) possible Sorted arrays and index-arithmetic-sensitive environments

Fibonacci search does not improve the asymptotic complexity of binary search. Its benefit is its structured partitioning and avoidance of midpoint calculations.

Generating the Fibonacci Numbers

The sequence used by the search can be generated using different approaches:

Approach Time Extra space Notes
Naive recursion O(phi^n), commonly bounded as O(2^n) O(n) recursion stack Recomputes overlapping subproblems
Memoization O(n) O(n) Each Fibonacci value is calculated once
Iterative generation O(n) O(1) Best choice for constructing the search boundaries
Matrix exponentiation O(log n) O(1) Efficient for very large indices
Fast doubling O(log n) O(log n) recursive stack Computes adjacent Fibonacci values efficiently

Binet’s formula can approximate Fibonacci numbers in constant time, but floating-point precision is lost for large n. Python integers do not overflow; other languages require 64-bit integers only through approximately F(92), with arbitrary-precision or big-integer support needed beyond that.

Code Example

def fibonacci_search(values: list[int], target: int) -> int:
    """Return the target's index in a sorted list, or -1 if it is absent."""
    if not values:
        return -1

    # Generate Fibonacci numbers until they cover the collection size.
    fibonacci = [0, 1]
    while fibonacci[-1] < len(values):
        fibonacci.append(fibonacci[-1] + fibonacci[-2])

    fibonacci_index = len(fibonacci) - 1
    left = 0

    while fibonacci_index > 2:
        middle = left + fibonacci[fibonacci_index - 1] - 1

        if middle >= len(values) or values[middle] > target:
            # Conceptually pad the array with values greater than the target.
            fibonacci_index -= 1
        elif values[middle] < target:
            left = middle + 1
            fibonacci_index -= 2
        else:
            return middle

    # At most one candidate remains.
    if left < len(values) and values[left] == target:
        return left

    return -1


example_values = [2, 5, 8, 13, 21]
print(fibonacci_search(example_values, 13))  # 3

Common Pitfalls

  • Unsorted input: The algorithm requires ascending order; otherwise, results are undefined.

  • Boundary errors: The probe can initially point beyond the actual array, so middle >= len(values) must be handled.

  • Duplicate values: Any matching duplicate may be returned; the function does not guarantee the first occurrence.

  • Edge cases: Empty and one-element collections are supported, and negative values work normally.

  • Integer overflow: Python integers are unbounded, but implementations in fixed-width languages must prevent index arithmetic from overflowing.

  • Common follow-up: Interviewers often ask why Fibonacci search is not asymptotically better than binary search, or request an O(1)-space implementation.

27

How do you implement Fibonacci Search and compare it with binary search?

Fibonacci Search is a search algorithm for sorted, randomly accessible collections that uses Fibonacci numbers to choose comparison positions. It has the same logarithmic asymptotic complexity as binary search, but its probe sequence differs and the shown implementation uses additional space for a Fibonacci table.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Using the standard definition (F(0)=0) and (F(1)=1):

  1. Generate Fibonacci numbers until the largest useful one covers the search interval.

  2. Let split be the largest Fibonacci number no greater than the current interval length.

  3. Compare the target with the element at low + split - 1.

  4. If it is equal, return the index.

  5. If the target is larger, search only the right interval.

  6. If the target is smaller, search only the left interval.

The interval shrinks according to Fibonacci proportions, so the number of comparisons is logarithmic.

Complexity and Comparison

The complexity figures below include algorithm setup and use auxiliary space, excluding the input collection.

Approach Best case Average case Worst case Auxiliary space
Fibonacci Search shown here (O(log n)) total (O(log n)) (O(log n)) (O(log n))
Standard binary search (O(1)) (O(log n)) (O(log n)) (O(1))

The Fibonacci table takes (O(log n)) time and (O(log n)) space to construct. The number of target-value comparisons can be (O(1)) in the best case and (O(log n)) on average or in the worst case. However, the shown code must decrement fib_index to locate the initial split, which takes (O(log n)) work, so total post-construction work remains (O(log n)).

Binary search halves the remaining candidate interval on each iteration. It stores only the two interval bounds, giving (O(1)) auxiliary space. A Fibonacci Search variant that locates its split without a stored table can also reduce auxiliary space to (O(1)).

Both algorithms are (O(log n)) and provide no asymptotic advantage over one another for ordinary sorted arrays. Binary search is usually simpler and has better space usage, while Fibonacci Search can be useful when its particular probe pattern matches the access pattern of the data structure.

Step-by-Step Example

For [1, 3, 5, 8, 13, 21, 34, 55, 89] and target 34:

  1. The interval length is 9; the largest Fibonacci number not exceeding it is 8.

  2. The first pivot is index 7, containing 55. Since 34 < 55, keep indices 0 through 6.

  3. The new interval length is 7; the largest Fibonacci number not exceeding it is 5.

  4. The next pivot is index 4, containing 13. Since 34 > 13, keep indices 5 through 6.

  5. The next split is 2, so the pivot is index 6, containing 34.

Fibonacci Sequence Context

Fibonacci values can also be generated with different time-space trade-offs:

Method Time Auxiliary space Notes
Naive recursion (O(phi^n)), often written (O(2^n)) (O(n)) Repeatedly calculates overlapping subproblems
Memoization (O(n)) (O(n)) Stores previously computed values
Iterative algorithm (O(n)) (O(1)) Keeps only the previous two values
Matrix exponentiation or fast doubling (O(log n)) (O(1)) iteratively or (O(log n)) recursively Best for very large indices

Binet’s formula computes Fibonacci numbers using floating-point arithmetic, but it loses precision for large n. Python integers do not overflow; in languages with signed 64-bit integers, F(92) is the last value that fits, so F(93) and later require a larger integer type.

Code Example

from collections.abc import Sequence


def fibonacci_search(values: Sequence[int], target: int) -> int:
    """Return a matching index in ascending values, or -1 if absent."""
    if not values:
        return -1

    fibonacci = [0, 1, 1]
    while fibonacci[-1] < len(values):
        fibonacci.append(fibonacci[-1] + fibonacci[-2])

    low = 0
    high = len(values)  # Exclusive upper bound
    fib_index = len(fibonacci) - 1

    while low < high:
        while fib_index >= 2 and fibonacci[fib_index] > high - low:
            fib_index -= 1

        split = fibonacci[fib_index]
        pivot = low + split - 1

        if values[pivot] == target:
            return pivot
        if values[pivot] < target:
            low = pivot + 1
        else:
            high = pivot

    return -1


def binary_search(values: Sequence[int], target: int) -> int:
    """Return a matching index in ascending values, or -1 if absent."""
    low = 0
    high = len(values)  # Exclusive upper bound

    while low < high:
        middle = low + (high - low) // 2

        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle

    return -1


data = [1, 3, 5, 8, 13, 21, 34, 55, 89]
print(fibonacci_search(data, 34))  # 6
print(binary_search(data, 34))    # 6

Common Pitfalls

  • Sorted input is required: Neither function sorts the collection.

  • Off-by-one errors: The code uses a half-open interval, [low, high), so high is exclusive.

  • Duplicates: The returned index is a valid match, but it is not guaranteed to be the first occurrence.

  • Empty and one-element inputs: Empty input returns -1; a one-element input is handled normally.

  • Negative values: They work correctly when the array is sorted numerically.

  • Input mutation: Neither function modifies the input collection.

  • Do not confuse search and sequence generation: Fibonacci Search finds an existing value in (O(log n)) time; calculating the nth Fibonacci number is a separate problem.

  • Common follow-up questions ask about removing the Fibonacci table, handling duplicates, and why binary search usually has better space efficiency.

28

Can Fibonacci recurrence optimize an algorithm's worst-case runtime?

Yes. Fibonacci-based optimization applies when an algorithm’s worst-case recurrence has the form T(n) = T(n-1) + T(n-2) + Θ(1), causing roughly Θ(φ^n) work. Memoization or dynamic programming eliminates repeated subproblems, reducing that cost to O(n), while fast doubling can compute the result in O(log n) arithmetic operations.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A naive recursive Fibonacci function follows:

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

Its number of calls satisfies a recurrence similar to the Fibonacci sequence, so the work grows exponentially. The key inefficiency is overlapping subproblems: computing F(5) calculates F(3) more than once.

Memoization stores previously calculated values so each Fibonacci number is computed once. Bottom-up dynamic programming performs the same optimization iteratively by retaining only the states needed to construct later values.

For very large n, fast doubling uses these identities:

  • F(2k) = F(k) × (2F(k+1) - F(k))

  • F(2k+1) = F(k)² + F(k+1)²

Because each step halves the index, only O(log n) doubling steps are required.

Approach Comparison

Approach Time Auxiliary space When to use
Naive recursion O(2^n), tighter Θ(φ^n); two recursive branches are repeatedly expanded O(n), including the recursion stack Demonstrating the problem
Memoized recursion O(n) expected; O(n²) pathological worst case with pervasive hash collisions O(n), including the cache and recursion stack Recursive solution with cached states
Bottom-up dynamic programming O(n); each state is calculated once O(n) for the table Simple, reliable linear-time solution
Two-variable iteration O(n); one update per Fibonacci number O(1) When O(n) time and constant auxiliary space are sufficient
Fast doubling O(log n) arithmetic operations; the index is halved each step O(1) iterative or O(log n) recursive Large inputs where logarithmic arithmetic operations are desired
Matrix exponentiation O(log n) arithmetic operations O(1) with iterative fixed-size matrices Fibonacci-like matrix recurrences

For deterministic implementations, best, average, and worst cases are identical except for the stated hash-table caveat. Space figures include any recursion stack but exclude the single input integer and returned result.

These bounds use the standard unit-cost integer model. Actual Python big-integer arithmetic has additional bit-level costs because F(n) contains Θ(n) bits.

Small Example

For F(5):

  1. F(5) requests F(4) and F(3).

  2. F(4) requests F(3) and F(2), repeating the calculation of F(3).

  3. Naive recursion expands this overlap until reaching F(1) and F(0).

  4. Memoization computes F(2) = 1, F(3) = 2, F(4) = 3, and F(5) = 5 once each.

  5. Fast doubling instead processes the binary digits of 5, requiring only three doubling steps.

Code Example

def fibonacci_dp(n: int) -> int:
    """Return F(n), where F(0)=0 and F(1)=1, using bottom-up DP."""
    if n < 0:
        raise ValueError("n must be non-negative")

    values = [0] * (n + 1)
    if n >= 1:
        values[1] = 1

    for index in range(2, n + 1):
        values[index] = values[index - 1] + values[index - 2]

    return values[n]


def fibonacci_fast(n: int) -> int:
    """Return F(n), where F(0)=0 and F(1)=1, using iterative fast doubling."""
    if n < 0:
        raise ValueError("n must be non-negative")

    previous, current = 0, 1

    for shift in range(n.bit_length() - 1, -1, -1):
        even_term = previous * (2 * current - previous)
        next_term = previous * previous + current * current

        if (n >> shift) & 1:
            previous, current = next_term, even_term + next_term
        else:
            previous, current = even_term, next_term

    return previous


print(fibonacci_dp(10))   # 55
print(fibonacci_fast(10)) # 55

Common Pitfalls

  • Assuming every algorithm benefits: The Fibonacci sequence is relevant only when the recurrence or runtime follows a Fibonacci-like pattern.

  • Ignoring recursion depth: Naive recursion quickly exceeds Python’s default recursion limit. Bottom-up DP or iterative fast doubling avoids this issue.

  • Using Binet’s formula with floats: F(n) = (φ^n - ψ^n) / √5 is mathematically valid, but floating-point implementations lose precision and can overflow for large n.

  • Ignoring integer limits: Python integers do not overflow. In languages such as Java or C++, signed 64-bit integers overflow starting around F(93); larger values require arbitrary-precision integers.

  • Handling edge cases: n = 0 returns 0, n = 1 returns 1, and negative n is invalid. Empty collections, duplicates, ordering, and graph-specific edge cases do not apply to this scalar input.

29

Prove sum of first n even-indexed Fibonacci numbers equals F(n+1) minus 1

The statement in the question contains an error: the sum of the first n even-indexed Fibonacci numbers F(0), F(2), …, F(2n‑2) equals F(2n‑1) − 1, not F(n+1) − 1. The proof below establishes the correct identity using mathematical induction with the standard definition F(0)=0, F(1)=1.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Correct Identity

For n ≥ 1: [ sum_{k=0}^{n-1} F(2k) = F(2n-1) - 1 ] - Even-indexed terms: F(0), F(2), F(4), …, F(2n‑2) (total n terms). - Right-hand side: the (2n‑1)st Fibonacci number minus 1. - The question’s claim F(n+1) − 1 only holds for n = 1 and n = 2 by coincidence.

Proof by Induction

Base case (n = 1)
Left side: F(0) = 0.
Right side: F(2·1‑1) − 1 = F(1) − 1 = 1 − 1 = 0. ✓

Inductive hypothesis
Assume the identity holds for some n = k ≥ 1: [ sum_{i=0}^{k-1} F(2i) = F(2k-1) - 1 ]

Inductive step (n = k + 1)
[ begin{aligned} sum{i=0}^{k} F(2i) &= left(sum{i=0}^{k-1} F(2i)right) + F(2k) \ &= bigl(F(2k-1) - 1bigr) + F(2k) quadtext{(by hypothesis)} \ &= F(2k-1) + F(2k) - 1 \ &= F(2k+1) - 1 quadtext{(Fibonacci recurrence } F(m)+F(m+1)=F(m+2)text{)} \ &= F(2(k+1)-1) - 1 end{aligned} ] Thus the identity holds for k+1. By induction, it holds for all n ≥ 1.

Step-by-Step Trace (n = 4)

Step Sum so far Term added New sum F(2n‑1) − 1
1 0 F(0)=0 0 F(1)−1=0
2 0 F(2)=1 1 F(3)−1=1
3 1 F(4)=3 4 F(5)−1=4
4 4 F(6)=8 12 F(7)−1=12

Computation Approaches

Approach Time Complexity Space Complexity When to Use
Naive Recursion O(φ^n) ≈ O(1.618^n) O(n) stack Teaching only; exponential time
Memoization / DP O(n) O(n) When multiple queries need caching
Iterative (bottom-up) O(n) O(1) Single computation, best for most cases
Matrix Exponentiation / Fast Doubling O(log n) O(log n) stack or O(1) iterative Very large n, competitive programming

Binet’s Formula

The closed-form Binet’s formula ( F(n) = frac{phi^n - psi^n}{sqrt{5}} ) with ( phi = frac{1+sqrt{5}}{2}, psi = frac{1-sqrt{5}}{2} ) gives the exact integer mathematically, but floating-point evaluation loses precision for n > 70 (double) or n > 100 (long double). Use integer methods for exact results.

Interview Tips

  • Clarify indexing: Confirm whether the sequence starts with F(0)=0 or F(1)=1, and whether “first n even-indexed” includes F(0).

  • Spot the typo: The question’s F(n+1) − 1 is incorrect for n ≥ 3; politely note the correct form F(2n‑1) − 1.

  • Induction structure: Always state base case, hypothesis, and step clearly; use the recurrence F(k)+F(k+1)=F(k+2) in the step.

  • Overflow: Python integers are arbitrary-precision; in C++/Java use 64-bit (up to n=92) or BigInteger/boost::multiprecision::cpp_int for larger n.

  • Follow-up: Interviewers may ask for the sum of odd-indexed terms (F(1)+F(3)+…+F(2n‑1) = F(2n)) or a matrix-exponentiation O(log n) computation.

30

How does Binet’s formula relate to Fibonacci numbers, and is it practical?

Binet’s formula gives a closed-form expression for Fibonacci numbers using powers of the golden ratio. Although mathematically exact, it is usually impractical for computing large Fibonacci numbers because floating-point arithmetic loses precision.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Relationship to Binet’s Formula

Using the standard definition:

  • F(0) = 0

  • F(1) = 1

  • F(n) = F(n - 1) + F(n - 2) for n ≥ 2

The characteristic equation of this recurrence is:

[ r^2 = r + 1 ]

Its roots are the golden ratio (phi = frac{1+sqrt5}{2}) and (psi = frac{1-sqrt5}{2}). Solving the recurrence with the initial values produces:

[ F(n) = frac{phi^n - psi^n}{sqrt5} ]

Because (|psi| < 1), the second term has a very small magnitude. Therefore, for every non-negative integer n:

[ F(n) = operatorname{round}left(frac{phi^n}{sqrt5}right) ]

For example, round(φ^5/√5) ≈ round(4.96) = 5, which is F(5).

Complexity Comparison

All bounds below are deterministic, so best, average and worst case are identical. Auxiliary space includes recursion stacks and caches but excludes the scalar input n; storage for the returned integer is noted separately.

Approach Time Auxiliary space When to use
Naive recursion (O(phi^n)), more precisely than (O(2^n)), because the recursion tree overlaps (O(n)) recursion stack Demonstrating exponential duplication only
Memoization (O(n)), because each Fibonacci value is calculated once (O(n)) cache Explaining overlapping subproblems
Iterative calculation (O(n)), due to one addition per term (O(1)) integer variables; the result itself needs (O(n)) bits Most practical solution for moderate n
Binet’s formula (O(log n)) exponentiation steps, but approximate (O(1)) floating-point variables Small values, estimates and mathematical analysis
Fast doubling (O(log n)) big-integer arithmetic operations (O(log n)) recursion stack Exact, efficient computation of large values
Matrix exponentiation (O(log n)) matrix multiplications (O(1)) matrices containing (O(n))-bit integers Similar performance to fast doubling

Strictly speaking, fast doubling’s bit-level running time is greater than (O(log n)) because each multiplication works with increasingly large integers.

Fast Doubling Example

Fast doubling uses these identities:

[ F(2k) = F(k)bigl(2F(k+1)-F(k)bigr) ]

[ F(2k+1) = F(k)^2 + F(k+1)^2 ]

Calculating F(10) recursively reduces the problem as follows:

Requested pair Result (F(n), F(n + 1))
pair(0) (0, 1)
pair(1) (1, 1)
pair(2) (1, 2)
pair(5) (5, 8)
pair(10) (55, 89)

Practical Considerations

  • Binet’s formula is useful mathematically, especially for deriving properties, approximations and growth behavior.

  • It is unreliable for exact large values: floating-point phi ** n / sqrt(5) loses precision, and sufficiently large powers may overflow.

  • Python integers do not overflow. They grow automatically, although arithmetic becomes more expensive as the number of bits increases.

  • In fixed-width languages, signed 64-bit integers can represent Fibonacci numbers through F(92); F(93) exceeds the signed 64-bit range. Larger values require big integers or overflow-safe designs.

  • For ordinary programming tasks, iterative calculation is often simplest. Fast doubling or matrix exponentiation is preferable when very large indices must be handled efficiently.

Common Pitfalls

  • Confusing the definitions F(0) = 0, F(1) = 1 with the alternative sequence starting 1, 1.

  • Using Binet’s formula with floating-point arithmetic and expecting exact results for large n.

  • Reporting only (O(log n)) for fast doubling without noting the cost of big-integer operations.

  • Forgetting that fixed-width integer overflow occurs near F(93) in signed 64-bit systems.

  • Common interview follow-ups ask for the derivation of Binet’s formula, the overlap in naive recursion, the fast-doubling identities, or the differences between arithmetic-operation and bit-level complexity.

32

How can you generate the Fibonacci sequence using two variables?

The two-variable iterative approach maintains the latest two Fibonacci numbers, yielding one and updating both after each step. It follows F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) without repeated recursive calls.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The recurrence is:

F(n) = F(n - 1) + F(n - 2)

Instead of storing the entire sequence internally, keep:

  • previous: the most recently yielded Fibonacci number.

  • current: the next Fibonacci number.

For each requested term:

  1. Yield previous.

  2. Update both values simultaneously.

  3. Repeat until the requested number of terms has been produced.

The simultaneous assignment is important: Python evaluates the right-hand side before changing either variable, so previous, current = current, previous + current correctly calculates the next pair.

Approach Comparison

These complexities use the standard unit-cost model, where each integer addition takes constant time. Extra space includes the recursion stack but excludes the input and returned output.

Approach Time Extra Space When to Use
Naive recursion O(2^n), more precisely O(phi^n) O(n) recursion stack Demonstrating overlapping recursive calls
Memoization O(n) O(n) cache and recursion stack Recomputing many overlapping subproblems
Two-variable iteration O(n) O(1) Generating terms sequentially
Matrix exponentiation or fast doubling O(log n) O(log n) recursively or O(1) iteratively Calculating one very large indexed term

Fibonacci is the classic example of overlapping subproblems: naive recursion repeatedly calculates the same F(n - 1) and F(n - 2) values. Memoization stores those results and reduces the work to O(n).

Binet’s formula can estimate F(n) in constant arithmetic time:

F(n) = (phi^n - psi^n) / sqrt(5)

However, it loses precision with floating-point values for large n, so it is unsuitable for exact large Fibonacci numbers.

Example Walkthrough

Generating seven terms:

Step Value yielded Updated (previous, current)
1 0 (1, 1)
2 1 (1, 2)
3 1 (2, 3)
4 2 (3, 5)
5 3 (5, 8)
6 5 (8, 13)
7 8 (13, 21)

The result is 0, 1, 1, 2, 3, 5, 8.

Code Example

from collections.abc import Iterator


def generate_fibonacci(term_count: int) -> Iterator[int]:
    """Yield term_count Fibonacci numbers starting with F(0) = 0."""
    if term_count < 0:
        raise ValueError("term_count must be non-negative")

    previous, current = 0, 1

    for _ in range(term_count):
        yield previous
        previous, current = current, previous + current


# Example:
print(list(generate_fibonacci(7)))
# [0, 1, 1, 2, 3, 5, 8]

The generator takes O(n) time and O(1) auxiliary space. The input is a single integer, so it occupies O(1) space. If the caller converts the generator into a list, the materialized output requires an additional O(n) stored values.

Common Pitfalls

  • Off-by-one errors: Clarify whether n means the index of the last term or the number of terms produced.

  • Empty input: generate_fibonacci(0) correctly produces no terms; a negative count raises ValueError.

  • One element: generate_fibonacci(1) produces [0], consistent with F(0) = 0.

  • Variable update order: Updating one variable before computing the other can produce incorrect values.

  • Integer overflow: Python integers do not overflow. Signed 64-bit integers in languages such as Java or C++ can store through F(92), but F(93) overflows; use arbitrary-precision integers beyond that point.

  • Space accounting: The iterative generator itself uses constant auxiliary space, but storing all generated terms changes the total output space to O(n).

33

How does Fibonacci analysis derive algorithm time complexity?

The Fibonacci sequence is a standard model for analyzing recursive algorithms whose recurrence splits into two smaller subproblems. With F(0) = 0 and F(1) = 1, it explains why naive recursion grows exponentially and why memoization, iteration, or fast doubling can produce substantially better complexities.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Fibonacci Models Recurrences

Many recursive algorithms have a recurrence such as:

T(n) = T(n - 1) + T(n - 2) + Θ(1)

The two recursive calls resemble the Fibonacci recurrence:

F(n) = F(n - 1) + F(n - 2)

To solve the recurrence, try a form proportional to r^n:

r^n = r^(n - 1) + r^(n - 2)

Dividing by r^(n - 2) gives:

r² = r + 1

The characteristic roots are:

φ = (1 + √5) / 2 ≈ 1.618
ψ = (1 - √5) / 2 ≈ -0.618

The dominant term is φ^n, so a recurrence with this structure has exponential growth. The usual O(2^n) bound is valid but loose; the more precise bound is Θ(φ^n).

This is why naive recursive Fibonacci is exponential: it repeatedly computes the same subproblems. For example, calculating F(5) requires F(4) and F(3), and both branches recompute overlapping values.

Approach Comparison

All approaches below are deterministic, so their best, average, and worst-case runtimes are the same for a given n.

Approach Time Auxiliary space When to use
Naive recursion O(2^n) loose; Θ(φ^n) precise O(n) recursion stack Demonstrating overlapping subproblems
Memoization O(n) O(n) table plus O(n) recursion stack Reusing previously computed results
Iterative computation O(n) O(1) Simple linear-time implementation
Matrix exponentiation O(log n) arithmetic operations O(1) with iteration Generalizing to matrix recurrences
Fast doubling O(log n) arithmetic operations O(1) with iteration Computing one Fibonacci number efficiently

The space figures are auxiliary space and exclude the input argument. In the standard unit-cost model, the input occupies one machine word. The returned integer is also excluded; because F(n) has Θ(n) bits, including output storage changes the bit-space analysis.

Fast Doubling Identities

Fast doubling computes F(n) using these identities:

F(2k)   = F(k) × (2F(k + 1) - F(k))
F(2k+1) = F(k)² + F(k + 1)²

The implementation processes the binary digits of n from left to right while maintaining the pair (F(k), F(k + 1)).

For n = 5, whose binary representation is 101, the states are:

  1. (F(0), F(1)) = (0, 1)

  2. After reading 1: (F(1), F(2)) = (1, 1)

  3. After reading 0: (F(2), F(3)) = (1, 2)

  4. After reading 1: (F(5), F(6)) = (5, 8)

The first value is F(5) = 5.

Code Example

def fibonacci(n: int) -> int:
    """Return F(n) using F(0) = 0 and F(1) = 1."""
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 0

    previous, current = 0, 1

    for bit_index in range(n.bit_length() - 1, -1, -1):
        doubled = previous * ((current << 1) - previous)
        doubled_next = previous * previous + current * current

        if (n >> bit_index) & 1:
            previous, current = doubled_next, doubled + doubled_next
        else:
            previous, current = doubled, doubled_next

    return previous


# Example: fibonacci(10) == 55

The algorithm performs O(log n) iterations, each containing a constant number of arithmetic operations. It uses O(1) auxiliary variables and has no recursion stack under the standard unit-cost model. Python integers do not overflow.

Binet’s formula is useful for understanding the mathematical growth:

F(n) = (φ^n - ψ^n) / √5

However, evaluating it with floating-point numbers loses precision for large n, so exact integer algorithms such as fast doubling are preferable. In languages with fixed-width integers, F(92) is the largest Fibonacci number that fits in a signed 64-bit integer; larger values require arbitrary-precision or appropriately sized integer types.

Common Pitfalls and Interview Tips

  • Use F(0) = 0 and F(1) = 1; other conventions shift the sequence.

  • Do not confuse the loose O(2^n) bound with the more precise Θ(φ^n) behavior.

  • Memoization fixes repeated work, but the recursion depth remains O(n).

  • Python integers avoid overflow; other languages may need 64-bit or big integers beyond n = 92.

  • Binet’s formula is mathematically exact but numerically unreliable for large inputs.

  • The function handles n = 0, n = 1, and negative inputs. It accepts one integer rather than a collection, so empty collections, duplicates, sorting, graph connectivity, and cycles are not applicable.

  • Interviewers commonly follow up by asking for the recurrence, characteristic-root derivation, memoization, or the fast-doubling identities.

34

How does Fibonacci demonstrate key computational complexity concepts?

The Fibonacci sequence is significant in computational complexity theory because its recurrence illustrates exponential growth, overlapping recursive subproblems, dynamic programming, and logarithmic-time matrix algorithms. It also demonstrates that an algorithm’s complexity depends on both the number of operations and the cost of handling increasingly large integers.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why It Matters

Using the standard definition, F(0) = 0 and F(1) = 1, with:

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

This sequence is important in complexity studies for several reasons:

  • Naive recursion is exponential: Calling F(n - 1) and F(n - 2) repeatedly computes the same values many times.

  • Overlapping subproblems: Fibonacci is the classic example used to motivate memoization and dynamic programming.

  • Linear recurrences support fast algorithms: Matrix exponentiation and fast doubling compute a term using logarithmically many arithmetic operations.

  • Output size matters: F(n) grows approximately as phi^n, where phi ≈ 1.618. Therefore, the exact result requires Θ(n) bits, so logarithmic arithmetic-operation count does not mean logarithmic total runtime with arbitrary-precision integers.

Recurrences and Formulas

The naive recursive recurrence has the time recurrence:

T(n) = T(n - 1) + T(n - 2) + O(1)

Its solution is O(phi^n), more precisely proportional to phi^n up to a constant factor.

Memoization evaluates each Fibonacci index only once, reducing the number of distinct subproblems from exponential to linear.

Fast doubling uses these identities:

  • F(2k) = F(k) × (2F(k + 1) - F(k))

  • F(2k + 1) = F(k)² + F(k + 1)²

It recursively computes the pair (F(k), F(k + 1)), where k = floor(n / 2), and then derives the requested term in constant arithmetic operations.

Binet’s formula is:

F(n) = round((phi^n - psi^n) / sqrt(5))

where psi = (1 - sqrt(5)) / 2. It is useful for studying growth, but floating-point calculations lose precision for large n, so it should not produce exact large Fibonacci numbers.

Approach Comparison

All approaches below have the same best, average, and worst-case cost because they are deterministic. Complexities use the standard unit-cost arithmetic model.

Approach Time Auxiliary Space When to Use
Naive recursion O(phi^n) O(n) recursion stack Demonstrating exponential recursion
Memoization O(n) O(n) cache and recursion stack Reusing results across overlapping calls
Iterative calculation O(n) O(1) auxiliary values Simple, readable linear solution
Matrix exponentiation O(log n) O(1) with iteration General linear recurrences
Fast doubling O(log n) O(log n) recursion stack Efficient Fibonacci-specific calculation

The input is a single integer and is not counted in auxiliary space. The returned output is also excluded from the table’s space figures; counting its exact bits gives Θ(n) output space.

Small Walkthrough

For n = 10, fast doubling follows 10 → 5 → 2 → 1 → 0:

Index n Computed pair (F(n), F(n + 1))
0 (0, 1)
1 (1, 1)
2 (1, 2)
5 (5, 8)
10 (55, 89)

At n = 10, k = 5:

  • F(10) = 5 × (2 × 8 - 5) = 55

  • F(11) = 5² + 8² = 89

Common Pitfalls

  • Off-by-one errors: Use F(0) = 0 and F(1) = 1; the recurrence applies only from F(2).

  • Invalid input: Negative Fibonacci indices are not defined under the standard sequence, so implementations typically reject them.

  • Floating-point arithmetic: Binet’s formula can round incorrectly for large n; use integer fast doubling instead.

  • Integer overflow: Python integers do not overflow. In other languages, signed 64-bit integers accommodate values through F(92); larger results require unsigned integers or arbitrary-precision integers.

  • Ignoring big-integer costs: Fast doubling performs O(log n) arithmetic operations, but multiplication and storage costs increase with the result’s Θ(n) bits.

  • Common follow-up questions: Interviewers may ask for an iterative solution, memoization, matrix exponentiation, modular Fibonacci numbers, or O(log n) time with O(1) auxiliary stack space.

35

Generate spiral matrix with Fibonacci numbers in Python

This task combines Fibonacci sequence generation with clockwise spiral filling to create an n × n matrix containing F(0) through F(n² - 1), starting at the top-left corner.

Read full answer

Applies toPython 3.12

Algorithm and Walkthrough

Use F(0) = 0 and F(1) = 1. Maintain four boundaries—top, bottom, left, and right—and fill the top row, right column, bottom row, and left column in that order. After each side, move its boundary inward so cells are not filled twice.

For n = 3:

  1. Fill the top row with 0, 1, 1.

  2. Fill the right column downward with 2, 3.

  3. Fill the bottom row right-to-left with 5, 8.

  4. Fill the left column upward with 13.

  5. Fill the center with 21.

The result is:

[[0, 1, 1],
 [13, 21, 2],
 [8, 5, 3]]

Fibonacci Generation Approaches

These bounds describe computing one Fibonacci term under unit-cost integer arithmetic:

Approach Time Auxiliary space When to use
Naive recursion O(phi^n), commonly stated as O(2^n) O(n) recursion stack Demonstrate repeated computation only
Memoization O(n) O(n) cache Reuse previously computed overlapping subproblems
Iterative two-variable generation O(n) O(1) Best default when generating many consecutive terms
Matrix exponentiation O(log n) O(1) with fixed-size matrices Compute one term at a very large index
Fast doubling O(log n) O(log n) recursively or O(1) iteratively Efficiently compute one large-index term

Memoization is Fibonacci’s classic example of overlapping subproblems: naive recursion repeatedly evaluates the same F(k) values, while caching each result prevents that duplication.

Binet’s formula, F(n) = round(phi^n / sqrt(5)), is useful for discussing closed-form approximations, but floating-point calculations lose precision for large n and are unsuitable for generating exact large integers.

Complexity Analysis

  • Time: Best, average, and worst case are all O(n²) under unit-cost integer arithmetic because each of the n² cells is written once and each Fibonacci update uses a constant number of arithmetic operations. Python’s arbitrary-precision arithmetic has additional bit-level costs for very large values.

  • Space: O(n²) integer cells for the returned matrix and O(1) auxiliary space, excluding the output and the scalar input. No recursion stack is used.

Code Example

def generate_fibonacci_spiral(n: int) -> list[list[int]]:
    """Return an n×n matrix filled with Fibonacci values in clockwise spiral order."""
    if n <= 0:
        return []

    matrix = [[0] * n for _ in range(n)]
    top, bottom = 0, n - 1
    left, right = 0, n - 1

    # a = F(k), b = F(k + 1)
    a, b = 0, 1

    def next_fibonacci() -> int:
        nonlocal a, b
        value = a
        a, b = b, a + b
        return value

    while top <= bottom and left <= right:
        # Left to right across the top row.
        for column in range(left, right + 1):
            matrix[top][column] = next_fibonacci()
        top += 1

        # Top to bottom down the right column.
        for row in range(top, bottom + 1):
            matrix[row][right] = next_fibonacci()
        right -= 1

        # Right to left across the bottom row.
        if top <= bottom:
            for column in range(right, left - 1, -1):
                matrix[bottom][column] = next_fibonacci()
            bottom -= 1

        # Bottom to top up the left column.
        if left <= right:
            for row in range(bottom, top - 1, -1):
                matrix[row][left] = next_fibonacci()
            left += 1

    return matrix


if __name__ == "__main__":
    print(generate_fibonacci_spiral(3))
    # Output: [[0, 1, 1], [13, 21, 2], [8, 5, 3]]

Common Pitfalls

  • Duplicate center writes: Missing boundary guards can cause the center cell to be filled more than once.

  • Off-by-one errors: The bottom-row range must include left, using left - 1 as its stop value.

  • Duplicate values: Repeated Fibonacci values are expected because F(1) = F(2) = 1.

  • Edge cases: This implementation returns [] for n <= 0 and [[0]] for n = 1.

  • Integer overflow: Python integers do not overflow. Signed 64-bit integers hold through F(92), but F(93) overflows.

Interview Tips

  • Explain how the iterative generator avoids recomputation and uses no recursion stack.

  • Be ready to adapt the direction to counter-clockwise order or change the starting position.

  • For an m × n matrix, use rows and columns, initialize bottom = rows - 1 and right = columns - 1, and keep the same while top <= bottom and left <= right condition.

  • Common follow-ups include fast doubling, generating only unique values, and returning an iterator instead of a complete matrix.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 35 Fibonacci Sequence answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects