Time Complexity of Memoization Fibonacci?

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?

Answers:

Answer

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

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).

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.