In a previous video, we have seen that the maximum depth of this recursive tree is going to be T divided
by m, where t is the target and m is the minimum value among the candidates given in the candidates
array.
Let's now see how we can make use of this to find the upper bound of the number of nodes in this recursive
tree.
In the previous video, we saw that if a tree is such that every node has three nodes.
And it goes on in this manner.
Then the maximum number of nodes that can be there in this tree would be equal to three to the power.
The height of this tree over here.
The maximum height of this tree plus one.
So in this same manner over here, the maximum number of nodes that can be there for every node is equal
to n, and therefore the maximum number of nodes in this recursive tree is equal to n to the power t
by m plus one.
Because t by m is the maximum height of this recursive tree.
So we have found the maximum number of nodes in this recursive tree.
And because in each node we are doing constant time operations, the time complexity of this approach
is of the order of n to the power t by m plus one into one, or just n to the power t by m plus one.
So this is the time complexity of this approach.
Now when it comes to the space complexity, it's going to be of the order of t divided by m, because
t by m is the maximum height or maximum depth of the recursive tree over here.
And and we will be using this space on the recursive call stack.
So the space complexity is of the order of t by m.
Also notice that the current array which is used to build each of these combinations, will also take
up space of the order of t by m, because t by m is the maximum size of the current array at any point.
So for example, over here, notice that this is the maximum size which is four elements.
The reason for this is the same reason as to why the maximum depth of this recursive tree over here
is t by m, because m is the minimum value.
And if we add m t by m times, we will either get a combination of coeur which is greater than the target
value or equal to the target value.
And this is going to be the largest instance for the current array.
So the time complexity is of the order of n to the power t by m plus one, and the space complexity
is of the order of T by m.
Now also do remember when we calculate the space complexity, we do not consider the space needed just
to hold the answer and return it as part of the space complexity.
So in this case, the results array also takes up space.
But we don't consider that as part of the space complexity.
And that's why the space complexity of this solution is of the order of T by.