Time complexity of this recursive python k-combination generator function

Question

I was looking for a python k-combination algorithm and found this little beauty here https://stackoverflow.com/a/2837693/553383

Any idea about its T(n) and/or time complexity?

Here is the code that you'll find in above link:

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

Answer 1

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