0
$\begingroup$

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}.

enter image description here

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

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wow, I cannot believe I overlooked that. Thank you for taking the time to answer my question so quickly and helping me clarify my doubts. I'm such a newb and definitely have more to learn. $\endgroup$ – dallasarch May 11 at 14:41
  • $\begingroup$ You have a great way to go! Keep learning, keep enjoying! $\endgroup$ – prime_hit May 11 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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