Time complexity of this code to list all subsets of a set?

Question

I have found numerous solutions across the web having O(2^n) complexity. Can someone help me figure out the time complexity of the code given below. Also it involves lot of bit manipulation and I am really weak in that area so I didn't quite get the hang of the code. Would be great if someone could explain the code.

private static void findSubsets(int array[])
{
  int numOfSubsets = 1 << array.length; 

  for(int i = 0; i < numOfSubsets; i++)
  {
    int pos = array.length - 1;
    int bitmask = i;

    System.out.print("{");
    while(bitmask > 0)
    {
      if((bitmask & 1) == 1)
         System.out.print(array[pos]+",");
     {
        bitmask >>= 1;
        pos--;
     }
     System.out.print("}");
  }
}

Is this the most optimal solution?

Answer 1

---

Time Complexity:

Here is an alternative way to derive the time complexity (compared to @templatetypedef).

Let M be the total number of steps in the code. Your outer for-loop runs 2^N times and the inner one runs log(i) times so we have:

Raise 2 to each side of the above equation and simplify:

Take the log of both sides of the above equation, and use Sterlings Approximation (Log(x!) ~ xLog(x) - x)

---

Bit Operations:

To address your weakness in bit manipulation you actually don't need it. It's used in three ways in your code, all of which can be replaced with less obfuscated functions:

1. Power of 2: (1 << array.length) → (Math.pow(2, array.length))
2. Divide by 2: (x >>= 1) → (x /= 2)
3. modulus 2: (x & 1) → (x % 2)

---

Code Explaination:

Also, to address the what the code is doing, it's essentially converting each number (0 to 2^N) into it's binary form using the method shown here, and as @templatetypedef states, 1 means that corresponding element is in the set. Here is an example of converting 156 to binary with this method:

As an example with your code:

pos = array.length - 1;
bitmask = 156;                              // as an example, take bitmask = 156
while(bitmask > 0){
    if(bitmask%2 == 1)                      // odd == remainder 1, it is in the set
         System.out.print(array[pos]+",");
    bitmask /= 2;                           // divide by 2
    pos--;
}

By doing this for all bitmasks (0 to 2^N) you are finding all unique possible sets.

---

EDIT:

Here is a look at the ratio (n2ⁿ/log₂(2ⁿ!) in sterling approximation you can see that it quickly approaches unity as n gets large:

Answer 2

This code works by using the connection between binary numbers with exactly n bits and subsets of a set of n elements. If you assign each element of the set to a single bit and treat "1" to mean "include the element in the subset" and "0" to mean "exclude the element from the subset," then you can easily convert between the two. For example, if the set contains a, b, and c, then 100 might correspond to the subset a, 011 to the subset bc, etc. Try reading through the code again with this insight.

In terms of efficiency, the above code is very fast both practically and theoretically. Any code that lists subsets has to spend some large amount of time just listing off those subsets. The time required is proportional to the total number of elements that have to be listed. This code spends O(1) work per item listed and therefore is asymptotically optimal (assuming, of course, that there aren't so many elements that you overflow the ints being used).

The total complexity of this code can be determined by counting how many total elements get printed. We can work out some math to solve this. Note that there are n choose 0 subsets of size 0, n choose 1 subsets of size 1, n choose 2 subsets of size 2, etc. Therefore, the total number of elements printed is given by

C = 0 × (n choose 0) + 1 × (n choose 1) + 2 × (n choose 2) + … + n × (n choose n)

Note that (n choose k) = (n choose n - k). Therefore:

C = 0 × (n choose n) + 1 × (n choose n - 1) + 2 × (n choose n - 2) + … + n × (n choose 0)

If we add these two together, we get

2C = n × (n choose 0) + n × (n choose 1) + … + n × (n choose n)

      = n × (n choose 0 + n choose 1 + … + n choose n)

The binomial theorem says that the parenthesized expression is 2ⁿ, so

2C = n2ⁿ

So

C = n2^n-1

So exactly n2^n-1 elements are printed, so the time complexity of this approach is Θ(n 2ⁿ).

Hope this helps!