# Complexity of generating all subsets of size $k$ using recursion

What is the complexity of the following (Python) code, that builds the list L of all subsets of size $$k$$ of a given set?

# arr: input array
# k  : size of subsets
# tmp : current subset
# idx : current index in tmp
# i : current array element
# L : list of all subsets of size k
def subsets(arr, k, idx, tmp, i, L = []):

if(idx == k):
L.append(tmp.copy())
return

# When no more elements are there to put in tmp[]
if(i >= len(arr)):
return

# current is included, put next at next location
tmp[idx] = arr[i]
subsets(arr, k, idx + 1, tmp, i + 1, L)

# current is excluded, replace it with next
# (i+1 is passed, but index is not changed)
subsets(arr, k, idx, tmp, i + 1, L)

return L

# Driver Code
if __name__ == "__main__":
arr = [10, 20, 30, 40, 50]
r = 3
print(subsets(arr, r, 0, [0]*r, 0))


Intuitively, the algorithm generates all the $$\binom{n}{k} = O(n^k)$$ such subsets ; but how to compute the complexity of this algorithm "rigorously" and not "intuitively"?

• Do you hear about master theorem Mar 26, 2023 at 11:35
• Yes, but Master Theorem applies on Divide and Conquer recursions, on the form $T(n) = a.T(n/b) + f(n)$. The recursion above is not of this form. Mar 26, 2023 at 11:57
• The usual method to evaluate the complexity of recursive algorithms is by establishing a recurrent equation.
– user16034
Mar 28, 2023 at 12:42
• @YvesDaoust Thx Yves, since my post, I indeed found information on solving those equations by the method of the characteristic equations Mar 29, 2023 at 9:10

The runtime of a recursive function can be expressed as a recurrence relation in terms of the sizes of its input parameters. Your recurrence begins with $$idx=0$$ and has a base case (stopping condition) of when $$idx=k$$. The quantity $$k-idx$$ starts high and the recursion stops when $$k-idx$$ reaches $$0$$.

So let $$T(n)$$ represent the runtime of your function on a difference of $$n=k-idx$$. It makes two recursive calls, both with the same $$k$$ and both with $$idx+1$$. So the difference $$k-idx$$ reduces by $$1$$ every recursion. And every recursive iteration makes two recursive calls. So we have $$T(n) = 2T(n-1)+c$$ where $$c$$ is the amount of steps used in each call frame (that is, $$c$$ counts the number of comparisons made for your base cases and the set-up of two new call frames and the return statement).

Now just solve $$T(n) = 2T(n-1)+c$$ subject to your base case (when $$n = k-idx = 0$$ it does 1 or 2 steps, whichever you are counting). So the base case of the recursion is $$T(0) = 1$$ (or $$2$$).

Both of these base cases result in solving the recurrence to $$T(n)=O(2^n)$$.

Note that your algorithm here is essentially producing all subsets (which is an $$\Theta(2^n)$$ process) and you are only keeping the ones that have $$k$$ items. So this implementation is doing more work than necessary. As an example, if you are finding all the 3-sets of an initial set of $$[1,2,3,4,5,6,7,8,9,10]$$ in order to get to $$[8,9,10]$$ you consider all the cases of $$1$$ being chosen or not, $$2$$ being chosen or not, $$3$$ being chosen or not, $$4$$ being chosen or not, etc.

You know how many results are produced. If you can determine how many operations each result takes, then you just multiply.

• That's essentially my question! :) Mar 26, 2023 at 11:59