1

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))
Community
  • 1
  • 1
Manis
  • 33
  • 5

1 Answers1

0

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

amit
  • 175,853
  • 27
  • 231
  • 333
  • I think your complexity calculation may leave out the cost of the slices in each recursive call. `elements[i+1:]` has running time `O(len(elements)-i)`, but I'm not sure how the numerous calls combine for each `i` and each level of the recursion. – Blckknght Apr 28 '14 at 23:27
  • @Blckknght Each recursive call is O(1) [some constant number of references are passes]. so you should have added an additive `k` factor, but that will just give you `O(n!/[(n-k)!k!] * k^2 + n!/[(n-k)!k!] * k)`, which is still in `O(n!/[(n-k)!k!] * k^2)`. The "bottle neck" in each combination creation is the iterative concat of elements to the tuple. – amit Apr 28 '14 at 23:29