First, given the (quite inefficient) algorithm for calculating the nth Fibonacci number below, determine its time complexity.
function fib(n) {
if (n === 0) {
return 0
}
else if (n === 1) {
return 1
}
return (fib(n - 1) + fib(n - 2))
}Second, given this additional algorithm for printing out all the Fibonacci numbers from 0 to n, determine its time complexity.
function allFib(n) {
for (let i = 0; i <= n; i++) {
console.log(fib(i))
}
}In the first part of the prompt, we should notice that the bulk of the time complexity in the function happens in the line when we return the sum of two recursive function calls. Since we have to work our way down from n to 0 step by step, you might at first think that this is a simple case of O(2n) => O(n). But notice that at each recursive step, we are not merely continuing to make two calls. Instead, the number of calls doubles at each step. (Those two recursive calls will each make two recursive calls, which will each make two recursive calls in turn.) So at first we are making two calls; then we are making four calls; then eight, etc.
This is a recognizable pattern! It's a binary tree.
That tells us that the time complexity of this set of recursive calls is approximately proportional to 2^n. (How do we know this? See the section below titled "How many nodes are in a binary tree?") That makes the time complexity of the whole function O(2^n), since only constant steps take place other than the recursive calls, and Big O lets us ignore constants.
What about the second function? At first glance, it seems like the second function is calling the first function n times, and therefore should have a time complexity of O(n*2^n). But the value of "n" being fed into the function fib as an argument is actually changing at each step of the for loop in the function allFib. It starts at 0, then increases by 1 until reaching the "n" being fed as an argument into allFib.
So the time complexity of allFib is actually the sum of the time complexities of the fib calls for each value of i: 2^0 + 2^1 + 2^3 + ... 2^n. This sum is equal to 2^(n + 1) - 1. (How do we know this? See the section below titled "How many nodes are in a binary tree?") This reduces to a time complexity of O(2^n) when you get rid of the constants, so the time complexity for allFib is the same as the time complexity for fib.
You may have heard before that when you have a recursive function that makes multiple calls, the runtime will often look like O(branches^depth), where branches is the number of times each recursive call branches. But why is this true? To reason it out, let's look at the binary tree image above. It takes the shape of a binary tree because the original function includes a line in which it calls itself twice. In most cases, each of those calls will then run a line that makes another two calls of the function itself (for a total of four), and so on.
You can imagine that if a function were to call itself three times, the branching would be tertiary instead of binary: each of the three recursive calls would call the function three times, and so on.
The math is simpler to see in the binary case, so let's focus on that. We can first ask, how deep will the tree go? In the case of the fib function, we know that the input has to work its way down from n to 0 (roughly), along both paths, so we can expect the tree to have approximately a depth of n. We then ask, how many nodes occur at each depth? Because each function calls itself twice, we know that the number of nodes will double at each successive level. At the zeroith level, we have 1 node; at the first level, we have 2 nodes; at the second level, we have 4 nodes, etc. The mathematical relationship between the depth and the number of nodes at that depth is therefore 2^d, where d is the level of depth.
At the deepest level (the nth level), then, we would expect to find approximately 2^n nodes. It might seem a bit counter-intuitive, at this point, that the total number of nodes be approximately 2^n, since there are obviously more nodes in the whole tree than just in the bottom level. But let's do the math.
If we were to sum up all the nodes at all the levels, we would get 2^0 + 2^1 + 2^2 + ... 2^(n - 1) + 2^n. Looking at this sum conceptually, we can think of it as 2^n + (2^n)/2 + (2^n)/4 + ... 2 + 1. Working our way up from the bottom level, each level contributes half of the nodes from the next lowest level to the total. The image below illustrates how such a sum will never be greater than two times 2^n, since each level (moving up) will never quite fill the second square.
In fact, if you work your way all the way down to 2^0, which equals 1, you will end up short of two times 2^n by exactly one, for a sum total of 2 * 2^(n) - 1, or 2^(n + 1) - 1 nodes. Recall that Big O doesn't care about constants, and this reduces to O(2^n).