Time Complexity of Memoization Fibonacci?

Question

I have the memoization fibonacci code and I am having trouble figuring out what the time complexity is of it:

function fibMemo(index, cache) {
  cache = cache || [];
  if (cache[index]) return cache[index];
  else {
    if (index < 3) return 1;
    else {
      cache[index] = fibMemo(index - 1, cache) + fibMemo(index - 2, cache);
    }
  }

  return cache[index];
}

What is the time complexity of this function?

Answer 1

Depends on what you mean.

Assuming the memoization was done correctly the number of "operations" will be the number of numbers generated. Which means the function runtime grows in relation to the amount of numbers you're trying to generate.

So it'll be O(n) where n is the number of numbers generated.

Answer 2

Assume T(n) is the time complexity of n, so T(n) = T(n-1) + T(n-2). Because F(n-2) is in the cache when we calculate F(n - 1), so the operation of F(n-2) is 1(reading from cache), so T(n) = T(n-1) + 1 = T(n-2) + 2 = ... = T(n-n) + n. And T(0) is 1, so T(n) = O(n + 1) = O(n).