Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question

Question

hope you all are doing well.

I have a question about the time complexity of solution 1 for question 16.4 - Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien.

The question instructs the reader to "Write a function that takes as input a set and returns its power set". The input is the set S = {0,1,2}.

I understand that there are at most 2^n recursive calls of the method directedSoFar. However, I don’t understand why we spend O(n) time within a call of directedSoFar. There are no loops inside the method, only 2 lines at the recursive case to add and remove elements into the current selectedSoFar solution, and another 2 lines at the base case. Doesn't this mean that we only spend constant time within a call, and not O(n) time?

I’ve struggled with this for a while, and have posted on the official forum as well as Reddit, but got no responses. I would appreciate it if anyone would be generous enough to help me.

Thank you

Answer 1

Note the following line of code:

powerSet.add(new ArrayList<>(SelectedSoFar);

Whenever we create a subset, we add the subset (list) to a list of list : power set. The size of subset will be $n$ (actually it will vary from $1$ to $n$, but we can take it to be $n$).

Even though adding a list requires one line of code, but it will involve copying all the elements. This is why it will take O(n) time.