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?

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.

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

.

©2020 All rights reserved.