Welcome back.
In this video, let's discuss the time and space complexity of the approach that we have taken to come
up with all the possible combinations where n and k are given to us.
Now, when it comes to the time complexity of a recursive solution, we have discussed that we can identify
it by multiplying the number of nodes in the recursive tree, with the work done at each individual
node to identify the number of nodes.
Let's make an observation notice over here that to get to each combination, we have to call the function
that we are recursively calling k times, or we need k nodes to identify each possible combination.
Notice over here this was one comma two comma three is a possible combination.
And to get to this we had to make three recursive calls to the function which we are using.
So to get to each combination we have to make k calls to the recursive function.
Or we need k nodes.
And when it comes to the number of combinations that are possible where n and k are given, we can find
it using n, c, k and c.
K is just a notation to indicate how many combinations can be made of length k.
When we use the numbers from one to n.
Now, using these two pieces of information, we can identify the number of nodes that are there in
the recursive tree.
And again we are just trying to find an upper bound.
And we are going to ignore overlaps.
So if we want to find an upper bound ignoring overlaps we can just multiply these two.
So the number of nodes will be k into n c k.
Now a quick side note on what n c k is.
Again this is a side note.
If we have n equal to four that's 1234.
And let's say k is equal to two.
We have seen that we can arrive at six combinations.
Now this six over here can also be calculated as 4C2.
Notice over here n is four because that's what's given.
And k is equal to two.
So we have two over here.
So we are writing n c k as 4C2 over here.
And the generic formula for n c k is n factorial by k factorial into n minus k factorial.
I'm sure this is something that you must have encountered in your mathematics classes, but over here
we are just having a quick side note again n factorial is one into two into three, etc. up to n.
So let's substitute this over here.
So we need n factorial.
And in this case n is four.
So we have four factorial in the numerator.
And then over here we need k factorial.
So that's this two factorial.
And then we need n minus k factorial which is this four minus two factorial.
So this simplifies to four factorial divided by two factorial into two factorial.
Now four factorial is four into three into two into one, which is 24, and two factorial is one into
two, which is two.
And again we have two factorial over here, which is two.
So 24 divided by four gives us six.
So that is why 4C2 is equal to six.
And in general terms to identify the possible number of combinations, all we need to do is we need
to identify n c k.
All right.
Now coming back to the approach that we discussed to identify the upper bound of the number of nodes,
we just need to multiply k and n c k.
Because for each combination we are making k calls to the recursive function that we will be writing.
And in total we'll be having n c k combinations.
Therefore, the number of nodes or the upper bound of the number of nodes will be k into n, c, k,
and in each call we are just doing constant time operations, which is like adding the value or appending
the value of j and then popping that value.
So in each call we are just doing constant time operations or O of one time complexity operations.
So this is why the time complexity of this solution is of the order of k into n c k and n c k, as we
have discussed, is n factorial divided by k factorial into n minus k factorial.
So the time complexity is of the order of k into n factorial by k factorial into n minus k factorial.
The space complexity of this solution is of the order of k, because.
Notice over here, the maximum depth of the recursive tree at any point is k, so the space complexity
is of the order of k because we are using space on the recursive call stack.
Do remember that we don't calculate the space required to return the answer as part of the space complexity,
because that's something the question asks us to do, and we would have to do that no matter what approach
we take.