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)$?