Runtime of this iterative combinations algorithm

Question

I have found the following algorithm online which, given a length n of an array and a number k of indices to select, produces all the possible combinations of k indices. I have implemented it here:

def combinations(n, k):
    combinations = []
    combination = [None]*k

    for i in range(k):
        combination[i] = i

    while combination[k - 1] < n:
        combinations.append(combination.copy())

        t = k - 1
        while t != 0 and combination[t] == n - k + t:
            t -= 1
        combination[t] += 1

        for i in range(t + 1, k):
            combination[i] = combination[i - 1] + 1

    return combinations


n, k = 4, 2
print(combinations(n, k))

(I am aware that Python's itertools could be used to produce this, however I aim to use this in Java, and have only written it in Python here for readability and easy testing.)

As an example, if we have an array [0,1,2,3] (with length n=4) and want to select k=2 indices, this will produce:

[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]

My time-analysis skills have grown a bit rusty: how would I go about determining the big-O runtime of this algorithm? Or, is this a well-known algorithm that anyone recognizes?

Answer 1

The trivial estimate is O(choose(n,k)*k), where choose(n,k) is the number of combinations. Indeed, the main while loop body is entered as many times as is the number of items in the answer. And each time, each of the two inner loops finishes in O(k).

There might be a tighter upper bound if n and k are in some special relation. For example, if k~n/2, I believe the k multiplier vanishes, leaving just O(choose(n,k)). But the bound is tight at least for the k=n-1 case.