Given a set {1,2,3} output { {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} } I have only been able to find as fast as O(2^n), is there any techniques for achieving faster results (besides parallelizing)
2 Answers
No.
Since there are 2^n subsets for a set with n items in it, and you have to print them all, your algorithm MUST perform the print step 2^n times (even if you tried to combine all the prints into one you would still have to "generate" the opening and closing braces 2^n times).
In fact we can look at something even lower level than printing an entire subset and determine that each particular item in the set will be printed exactly (2^n)/2 times. There are 2^n subsets and each item is in exactly half of them. This operation is even lower level than printing an entire set and we can see that it is O(2^n)
- what about just generating the subsets without actually printing?Jamil Seaidoun– Jamil Seaidoun2014-04-29 23:03:13 +00:00Commented Apr 29, 2014 at 23:03
- 3What does it mean to "Generate the subsets"? You could create a 'lazy sequence' of the subsets in constant time, however anything that iterates over all the subsets in any way must be at least O(2^n) because it involves iterating over O(2^n) sets. Generating possibly the most efficient representation of the sets (an integer of n bits where each bit represents the presence or absence of the nth item of the set) still requires you to generate O(2^n) integers.WuHoUnited– WuHoUnited2014-04-30 02:41:52 +00:00Commented Apr 30, 2014 at 2:41
- yeah thats what I thought, i was mostly talking about creating the subsets, but as far as I could find it's still O(2^n). Thanks!Jamil Seaidoun– Jamil Seaidoun2014-04-30 19:01:00 +00:00Commented Apr 30, 2014 at 19:01
In response to generating subsets without actually printing I believe you mean finding the subsets and then storing them one by one into a result list/array. In that case the runtime would be O(n*2^n). The O(2^n) is from finding all the subset. After finding them you THEN need to store them into an array and to do that we need to look at each subset (which we know must be of size n) and that takes O(n) to copy as it needs to look at each element of the subset and copy it into your results array.
You can think of it this way, we need to store the subsets we found 2^n times since thats how many of those subsets existed. And we need to copy this subset (O(n) time complexity) that many times.
