Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
I dint understand how's the time complexity of creating subsets is O(N*2^N). Can...

Supreet Sandhu

Mar 5, 2022

I dint understand how's the time complexity of creating subsets is O(N*2^N). Can someone please help me understanding? Thanks!

0

0

Comments
Comments
Design Gurus
Design Gurus4 years ago

The idea is to calculate how many total iterations the code is doing. Try calculating it (before reading below).

Here is how we can calculate this.

The first 'for' loop runs 'N' time, where 'N' is the total number of elements in the input array.

Now the difficult par...

J
justanothercoder 3 years ago

Its not really clear how this uses a BFS .. can you please elaborate

S
Smoke 3 years ago

Same here. Does anyone care to explain?

Design Gurus
Design Gurus3 years ago

In BFS we traverse all nodes on the same level before moving on the next level. Similar approach is used here.

The nested 'for' loop takes all subsets generated in the previous steps (or level) to create new subsets.

Normally in BFS, we only deal with elements generat...