Fibonacci Number

Q: What is the time complexity of the recursive Fibonacci function?

The naive recursion makes 2 × F(n+1) - 1 calls, a count that grows like 1.618^n and is usually written O(2^n) . For n = 45 that is about 3.7 × 10^9 calls. Storing each result once, in a table or in two variables, brings it down to O(n) .

Q: How do you solve Fibonacci with dynamic programming?

Start from the recurrence F(n) = F(n-1) + F(n-2) and compute the values in increasing order of n , storing each one. You can fill a table from the bottom up, or keep the recursive function and cache its results, which is called memoization. Either way each value is computed once, so the total work is O(n) .

Q: Can Fibonacci be computed in O(1) space?

Yes. Each number depends only on the two before it, so two variables are enough. Keep the last two values and slide them forward on every step. That gives O(n) time with O(1) extra space.

Q: Is there a faster way than O(n)?

Yes. The matrix [[1, 1], [1, 0]] raised to the power n holds F(n) in its top right corner, and repeated squaring computes that power in O(log n) matrix multiplications. A closed formula with powers of the golden ratio also exists, but it works in floating point and loses precision as n grows, so the integer methods are preferred.

BeginnerDynamic programming Recursion

+10

The Fibonacci numbers start with F(0) = 0 and F(1) = 1, and every later number is the sum of the two before it: F(n) = F(n-1) + F(n-2). The sequence begins 0, 1, 1, 2, 3, 5, 8, 13. Your function gets n and returns F(n).

Function

fib(n: integer) → integer

ninteger: the position in the Fibonacci sequence, counting from 0
Returnsinteger: the Fibonacci number F(n)

Constraints

0 ≤ n ≤ 45
The answer fits in a signed 32-bit integer: F(45) = 1134903170.

Examples

Input: n = 4
Output: 3
Explanation: Count up from the start: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, and F(4) = 2 + 1 = 3.

Input: n = 10
Output: 55
Explanation: The sequence from index 0 runs 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. The number at index 10 is 34 + 21 = 55.

+13 hidden tests on Submit

Follow-up

Can you compute F(n) in O(log n) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The definition is already a recursive function, and writing it as one gives the right answer. The trap is the running time: the two recursive calls redo each other's work, and the number of calls grows exponentially with n. Dynamic programming fixes that by computing each Fibonacci number once, from the bottom up. The last step keeps only the two numbers the next one needs.

Recursion straight from the definition

Correct, but does not finish on the largest tests

Intuition

Translate the definition word for word. fib(0) is 0, fib(1) is 1, and anything larger returns fib(n-1) + fib(n-2). Every chain of calls ends in one of the two base cases, so the answer is correct.

Now count the calls. fib(5) calls fib(4) and fib(3), but fib(4) calls fib(3) again. In the end fib(3) runs twice, fib(2) three times and fib(1) five times, and fib(5) makes 15 calls in total. The same values are recomputed over and over.

The call count follows the Fibonacci numbers themselves: computing F(n) makes 2 × F(n+1) - 1 calls. For n = 45 that is about 3.7 × 10^9 calls, far too many for a time limit. The bound is usually written O(2^n); the exact growth is about 1.618^n. The recursion is only n levels deep, so the stack needs O(n) space.

Algorithm

If n is 0 or 1, return n.
Otherwise call the function on n-1 and on n-2.
Return the sum of the two results.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

Fill a table from the bottom up

Intuition

The recursion is slow only because it forgets. If you write each Fibonacci number down the first time you compute it, each one costs a single addition. Make a table f with slots for indexes 0 to n, set f[0] = 0 and f[1] = 1, and fill the rest from left to right with f[i] = f[i-1] + f[i-2].

The left to right order is what makes it work: when you reach f[i], both numbers it needs are already in the table. For n = 10 the table fills as 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and the answer is the last slot.

This is dynamic programming in its plainest form, a recurrence plus a table of answers to smaller cases. There are n-1 additions, O(n) time, and the table holds n + 1 numbers, O(n) space. n = 45 now takes 44 additions instead of billions of calls.

Algorithm

If n is 0 or 1, return n.
Create a table of n + 1 numbers with f[0] = 0 and f[1] = 1.
For i from 2 to n, set f[i] = f[i-1] + f[i-2].
Return f[n].

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

Keep only the last two numbers

Intuition

Look at what the table loop reads. To fill f[i] it needs f[i-1] and f[i-2] and nothing older, so every earlier slot is dead weight. Keep two variables instead of a table: prev holds the number two steps back and curr the number one step back.

Start with prev = 0 and curr = 1, which are F(0) and F(1). On each step compute next = prev + curr, then slide the pair forward: prev takes the old curr, and curr takes next. For n = 4 the pair moves from (0, 1) to (1, 1), (1, 2) and (2, 3), and curr = 3 is the answer.

The work is the same n-1 additions, O(n) time, with three integers in memory, O(1) space. The order of the updates matters: if you overwrite prev before adding it, the sum uses the wrong value.

Algorithm

If n is 0 or 1, return n.
Set prev = 0 and curr = 1.
Repeat n-1 times: compute next = prev + curr, then set prev = curr and curr = next.
Return curr.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Pitfalls and edge cases

Fibonacci is the classic first dynamic programming problem, and most bugs come from the recursion or from the first two values.

Handing in the naive recursion. It passes small tests and then needs billions of calls at n = 45. Store results in a table or in two variables.
Getting the start wrong. Here F(0) = 0 and F(1) = 1, so F(2) = 1 and F(10) = 55. Starting the sequence at 1, 1 shifts every answer by one index.
Building the table without a guard for small n. For n = 0, a table of size n + 1 = 1 has no slot for f[1], and writing it is out of bounds. Return n at once when n < 2.
Updating the pair in the wrong order. prev = curr followed by curr = prev + curr adds the new prev and doubles curr. Compute the sum into next first, or use a simultaneous assignment where the language has one.
Running one step too far. A loop that also computes F(n+1) reaches F(46) = 1836311903 at the limit, which still fits in 32 bits only by luck. F(47) does not.

Frequently asked questions4

What is the time complexity of the recursive Fibonacci function?

The naive recursion makes 2 × F(n+1) - 1 calls, a count that grows like 1.618^n and is usually written O(2^n). For n = 45 that is about 3.7 × 10^9 calls. Storing each result once, in a table or in two variables, brings it down to O(n).

How do you solve Fibonacci with dynamic programming?

Start from the recurrence F(n) = F(n-1) + F(n-2) and compute the values in increasing order of n, storing each one. You can fill a table from the bottom up, or keep the recursive function and cache its results, which is called memoization. Either way each value is computed once, so the total work is O(n).

Can Fibonacci be computed in O(1) space?

Yes. Each number depends only on the two before it, so two variables are enough. Keep the last two values and slide them forward on every step. That gives O(n) time with O(1) extra space.

Is there a faster way than O(n)?

Yes. The matrix [[1, 1], [1, 0]] raised to the power n holds F(n) in its top right corner, and repeated squaring computes that power in O(log n) matrix multiplications. A closed formula with powers of the golden ratio also exists, but it works in floating point and loses precision as n grows, so the integer methods are preferred.