1
$\begingroup$

I'm trying to analyse the time complexity of the following algorithm for generating the power set:

 public static List<List<Integer>> generatePowerSet(List<Integer> inputSet) {
    List<List<Integer>> powerSet = new ArrayList<>();
    directedPowerSet(inputSet, 0, new ArrayList<Integer>(), powerSet);
    return powerSet;
  }

  private static void directedPowerSet(List<Integer> inputSet, int toBeSelected,
                                       List<Integer> selectedSoFar,
                                       List<List<Integer>> powerSet) {
    if (toBeSelected == inputSet.size()) {
      powerSet.add(new ArrayList<>(selectedSoFar));
      return;
    }
    selectedSoFar.add(inputSet.get(toBeSelected));
    directedPowerSet(inputSet, toBeSelected + 1, selectedSoFar, powerSet);
    selectedSoFar.remove(selectedSoFar.size() - 1);
    directedPowerSet(inputSet, toBeSelected + 1, selectedSoFar, powerSet);
  }

It generates the power set as a union of all subsets that include a particular element (toBeSelected) and those subsets that don't.

Let $n$ be the size of the sub list [inputSet, inputSet.size()-1] and let $N$ be the size of inputSet which never changes in subsequent recursive calls. The recurrence relation is

$T(n)=\begin{cases}\mathcal{O}(N) \mbox {, if n=0}\\2T(n-1)+\Theta(1)\end{cases}$

By analysing the recursion tree we can see that $T(n) = 2^n*\mathcal{O}(N)+2^{n-1}+\ldots+1= \mathcal{O}(N2^n)$.

I'm a bit concerned about $N$ in the answer, some analyses that I've seen just say it's $\mathcal{O}(n2^n)$. My problem with it is that if we take $n$ as the size of the original input the recurrence doesn't make sense - $n$ doesn't change from call to call. If we take $n$ as the sub lists's size the we end up with $N$ in the base case's runtime, also $N$ is a constant, in which case is the base case in $\mathcal{O}(1)$ and the algorithm's time is just $\mathcal{O}(2^n)$? Doesn't make sense too. Should we consider $T$ as a function of two variables $T(N, n)$?

$\endgroup$
1
  • $\begingroup$ Your analysis is correct, and it would be cleaner to use the 2-parameter recurrence relation as you suggest in the last sentence. But I object to your claim that N is constant just because it's not in the recurrence. $\endgroup$
    – Pål GD
    Nov 28, 2021 at 20:42

1 Answer 1

1
$\begingroup$

You are right that in order to analyze the recurrence, you need to take two parameters into account: the original list size $N$, and the size of the sublist currently operated on $n$. In terms of these parameters, the running time is $\Theta(N2^n)$.

However, what we are really interested in is the running time of the algorithm when running on the entire list (in your snippet, the running time of the first procedure rather than the second procedure); the fact that the algorithm proceeds recursively is an implementation detail. In other words, when analyzing the algorithm, there is only one parameter, namely the input size $n$. Therefore we can safely identify $N$ and $n$ in the final formula, and conclude that the running time is $\Theta(n2^n)$, where $n$ is the input size.

Stated differently, our end goal is understanding the running time of the algorithm (your first procedure) as a function of the input size. This analysis involves analyzing a certain recursive procedure (your second procedure), whose analysis involves both the original input size and the current input size. The final conclusion is that if we run the recursive procedure on an array of size $n$, then its running time is $\Theta(n2^n)$, and this is what we care about. The more refined running time $\Theta(N2^n)$ only shows up as part of the analysis, but is not reflected in the final result.

$\endgroup$

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.