I am having trouble with simplifying the time complexity for this recursive algorithm for finding the Power-Set of a given Input Set. I not entirely sure if what I have got is correct so far either.

It's described at the bottom of the page in this link: http://www.ecst.csuchico.edu/~akeuneke/foo/csci356/notes/ch1/solutions/recursionSol.html

By considering each step taken by the function for an arbitrarily chosen Input Set of size 4 and then translating that to an Input Set of size n, I came to the result that the time complexity in terms of Big-O notation for this algorithm is: 2ⁿnⁿ

Is this correct? And is there a specific way to approach finding the time-complexity of recursive functions?

CodePudding user response：

The run-time is actually O(n*2ⁿ). The simple explanation is that this is an asymptotically optimal algorithm insofar as the total work it does is dominated by creating the subsets which feature directly in the final output of the algorithm, with the total length of the output generated being O(n*2ⁿ). We can also analyze an annotated implementation of the pseudo-code (in JavaScript) to show this complexity more rigorously:

function powerSet(S) {
  if (S.length == 0) return [[]]  // O(1)
  let e = S.pop()                 // O(1)
  let pSetWithoutE = powerSet(S); // T(n-1)
  let pSet = pSetWithoutE         // O(1)
  pSet.push(...pSetWithoutE.map(set => set.concat(e))) // O(2*|T(n-1)|   ||T(n-1)||)
  return pSet; // O(1)
}
// print example:
console.log('{');
for (let subset of powerSet([1,2,3])) console.log(`\t{`, subset.join(', '), `}`);
console.log('}')

Where T(n-1) represents the run-time of the recursive call on n-1 elements, |T(n-1)| represents the number of subsets in the power-set returned by the recursive call, and ||T(n-1)|| represents the total number of elements across all subsets returned by the recursive call.

The line with complexity represented in these terms corresponds to the second bullet point of step 2. of the pseudocode: returning the union of the powerset without element e, and that same powerset with every subset s unioned with e:

(1) U ((2) = {s in (1) U e})

This union is implemented in terms of push and concat operations. The push does the union of (1) with (2) in |T(n-1)| time as |T(n-1)| new subsets are being unioned into the power-set. The map of concat operations is responsible for generating (2) by appending e to every element of pSetWithoutE in |T(n-1)| ||T(n-1)|| time. This second complexity corresponds to there being ||T(n-1)|| elements across the |T(n-1)| subsets of pSetWithoutE (by definition), and each of those subsets being increased in size by 1.

We can then represent the run-time on input size n in these terms as:

T(n) = T(n-1)   2|T(n-1)|   ||T(n-1)||   1; T(0) = 1

It can be proven via induction that:

|T(n)| = 2n 
||T(n)|| = n2n-1

which yields:

T(n) = T(n-1)   2*2n-1   (n-1)2n-2   1; T(0) = 1

When you solve this recurrence relation analytically, you get:

T(n) = n   2n   n/2*2n = O(n2n)

which matches the expected complexity for an optimal power-set generation algorithm. The solution of the recurrence relation can also be understood intuitively:

Each of n iterations does O(1) work outside of generating new subsets of the power-set, hence the n term in the final expression.

In terms of the work done in generating every subset of the power-set, each subset is pushed once after it is generated through concat. There are 2ⁿ subsets pushed, producing the 2ⁿ term. Each of these subsets has an average length of n/2, giving a combined length of n/2*2ⁿ which corresponds to the complexity of all concat operations. Hence, the total time is given by n 2ⁿ n/2*2ⁿ.