16.4 Generate Power Set - solution 1 time complexity question

#1

Hi everyone,

For solution 1 of 16.4 Generate Power Set, I understand that there are 2^n recursive calls. However, I don’t understand why we spend O(n) time within a call. There are no loops inside the method, only 2 lines to add and remove elements into the current selectedSoFar solution. I’ve struggled with this for a while, and I would appreciate it if anyone would be generous enough to help me.

Thank you

0 Likes
#2

Hi @wjin,

I’m also having a hard time to understand why we spend O(n) time within a call here, could you share if you figured out this?

0 Likes
#3

Hi, I figured it out by asking the question over at CS Stackexchange. Here was the question I posted a while back: https://cs.stackexchange.com/questions/125539/elements-of-programming-interviews-16-4-generate-power-set-solution-1-time-c

0 Likes
#4

Hi @wjin, thank you for the answer!

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

This part came to my mind but only leaves of the recursion tree will execute this step so I wasn’t sure about this; cause I thought it should be something which is executed at every recursive call.

However number of leaves of the recursion tree of generating a power set is 2^n. So I guess stackexchange answer is correct.

Thank you for posting this question :slight_smile:

0 Likes