Fibonacci Memoization Time Complexity?

Question

I have memoization fibonacci code and am having trouble figuring out its complexity:

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 that memoization was done correctly, the number of "operations" will be the number of numbers generated. This means that the execution time of the function grows in relation to the number of numbers you are trying to generate.

So this will be O (n), where n is the number of generated numbers.