Time complexity of this combination algorithms

user_1377711 0
Viewed 2615

I was implementing a combinations algorithm. This should generate unique combinations of length from the given list .

For example:

Input list [1, 2, 3, 4, 5] with k = 3
should generate output

    [1, 2, 3]
    [1, 2, 4]
    [1, 2, 5]
    [1, 3, 4]
    [1, 3, 5]
    [1, 4, 5]
    [2, 3, 4]
    [2, 3, 5]
    [2, 4, 5]
    [3, 4, 5]

The working python code is given below for reference.

def my_combinations(items, k, out):
    if k==0:
        print out
        return

    for i in range(len(items)):
        new_out = out[:]
        new_out.append(items[i])
        my_combinations(items[i+1:], k-1, new_out)

Question:

What is the time complexity of this algorithm?

I started with the recurrence equation.

Base case: T(n, 0) = 1
Recurion : T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1) + .. + T(0, k-1) + 1
                   = n * T(n-1, k-1) + 1

T(n) = ???

solution by expansion.

This question is different from the Complexity when generating all combinations.

My question is about the time complexity of the given implementation and the link question talks about runtime of generating all combinations in general.

recursion algorithm python
1 Answers

Thanks @Michael Foukarakis for pointing the missing K.

Base case: T(n, 0) = 1
Recurion : T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1) + .. + T(0, k-1) + 1
                   = n * T(n-1, k-1) + 1

Expanding it as below

T(n, k) = n * T(n-1, k-1) + 1
        = n * (n-1) * T(n-2, k-2) + 1 + 1
        = n * (n-1) * T(n-2, k-2) + 2
        = n * (n-1) * (n-2) * T(n-3, k-3) + 3

        ...

         = n * (n-1) * (n-2) * ..(n-k) T(n-k, k-k) + k
         = n * (n-1) * (n-2) * ..(n-k) (1) + k
         = O(n^k)  (As it is a k th order polynomial)

Overall we can say O(nk) runtime.

user_13777110
Related