Fibonacci: Two Implementations Compared

Reported in interviews at BlackRock

Problem statement

Compute the $n$-th Fibonacci number, defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$.

Implement the function:

def fib(n):
    ...

It takes a single non-negative integer n and returns the $n$-th Fibonacci number as an int.

For discussion, consider two implementations -- for example naive recursion versus an iterative (or memoized) version -- and compare their time and space complexity.

Example

fib(6) -> 8 because the sequence is $0, 1, 1, 2, 3, 5, 8$, so index 6 (0-based) is 8. Likewise fib(10) -> 55.

Show hint

If you draw the call tree of the textbook recursive definition, how many times does the same subproblem appear?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems