Number of calls

Report a typo

Here is our pseudocode to find the nn-th Fibonacci number using memoization:

function fib(n):
    numbers = array[0, n]
    for i in [0, n]:
        numbers[i] = -1
    return fib_helper(n, numbers)

function fib_helper(n, numbers):
    if numbers[n] != -1:
        return numbers[n]
    if n < 2:
        numbers[n] = n
    else:
        numbers[n] = fib_helper(n-1, numbers) + fib_helper(n-2, numbers)
    return numbers[n]

Assume that we apply the described fib function for n=6n=6. How many values from the numbers array will fib_helper reuse?

Enter a number
___

Create a free account to access the full topic