0
$\begingroup$

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"?

$\endgroup$
4
  • $\begingroup$ Do you hear about master theorem $\endgroup$
    – ClickName
    Mar 26, 2023 at 11:35
  • $\begingroup$ 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. $\endgroup$
    – Greg82
    Mar 26, 2023 at 11:57
  • $\begingroup$ The usual method to evaluate the complexity of recursive algorithms is by establishing a recurrent equation. $\endgroup$
    – user16034
    Mar 28, 2023 at 12:42
  • $\begingroup$ @YvesDaoust Thx Yves, since my post, I indeed found information on solving those equations by the method of the characteristic equations $\endgroup$
    – Greg82
    Mar 29, 2023 at 9:10

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ That's essentially my question! :) $\endgroup$
    – Greg82
    Mar 26, 2023 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.