Assuming this function indeed generates all possible combinations of length k
, its time complexity of this function is O(n!/[(n-k)!k!] * k^2)
.
There are exactly O(n!/[(n-k)!k!])
k-combinations, and we generate each of them.
Let's look on the geration of each. It is done by creating a tuple iteratively. First the 1st element is added, then the 2nd, then the 3rd and so on.
However, cretaing a tuple of length k
is O(k)
, and we actually get O(1+2+...+k)
for each tuple creation. Since O(1+2+...+k)=O(k^2)
, and we do that for each tuple, we can conclude that the total complexity of this function is O(n!/[(n-k)!k!] * k^2)
.