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: