Time Complexity of Memoization Fibonacci?

Without memoization

I think that it's helpful to have a picture in your head of what the call tree looks like when you don't use memoization. For example, this is what it looks like for fib(5):

What's the time complexity of this algorithm? Well, how many times are we calling fib()? To answer that question, think about each level of the tree.

The first level has one call: fib(5). The next level has two calls: fib(4) and fib(3). The next level has four. So on and so forth. Each node is branching off into two additional nodes, so it's 2*2*2... = 2^n. Well, it's O(2^n), it's usually not exactly 2^n. You can see that here where level 4 is missing a node and level 5 only has one node.

With memoization

Now think about what it would look like with memoization. When you use memoization, you're remembering results that you've previously computed. So it'll look like this:

The ones with the squares around them are just returning the memoized result. If you ignore them, you can see that the algorithm is just being called once for each value from 0 to n.

Well, fib(1) does get called a one "extra" times, but since we're thinking about big-O here, it doesn't change things. Same with the calls with the squares around them. Even if we wanted to include them, it would still be O(n).

To prove that to yourself and make it intuitive, try writing out a call tree for something larger than fib(5). Maybe fib(10) or fib(20). You'll see that if you squint your eyes, it basically takes the form of a diagonal line moving down and to the left. There may be a few extra branches sprouting out here and there, but basically, it's a line.

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