Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the running time of this powerset algorithm

I have an algorithm to compute the powerset of a set using all of the bits between 0 and 2^n:

public static <T> void findPowerSetsBitwise(Set<T> set, Set<Set<T>> results){
        T[] arr = (T[]) set.toArray();
        int length = arr.length;

        for(int i = 0; i < 1<<length; i++){
            int k = i;
            Set<T> newSubset = new HashSet<T>();
            int index = arr.length - 1;
            while(k > 0){
                if((k & 1) == 1){
                    newSubset.add(arr[index]);
                }
                k>>=1;
                index --;
            }
            results.add(newSubset);
        }

    }

My question is: What is the running time of this algorithm. The loop is running 2^n times and in each iteration the while loop runs lg(i) times. So I think the running time is

T(n) = the sum from i=0 to i=2^n of lg(i)

But I don't know how to simplify this further, I know this can be solved in O(2^n) time (not space) recursively, so I'm wondering if the method above is better or worse than this, timewise as it's better in space.

like image 445
Aly Avatar asked May 21 '11 21:05

Aly


2 Answers

sigma(lg(i)) where i in (1,2^n) 
= lg(1) + lg(2) + ... + lg(2^n)     
= lg(1*2*...*2^n) 
= lg((2^n)!) 
> lg(2^2^n) 
  = 2^n

thus, the suggested solution is worth in terms of time complexity then the recursive O(2^n) one.


EDIT:
To be exact, we know that for each k - log(k!) is in Theta(klogk), thus for k=2^n we get that lg((2^n)!) is in Theta(2^nlog(2^n) = Theta(n*2^n)

like image 186
amit Avatar answered Nov 15 '22 07:11

amit


Without attempting to solve or simulate, it is easy to see that this is worse than O(2^n) because this is 2^n * $value where $value is greater than one (for all i > 2) and increases as n increases, so it is obviously not a constant.

like image 28
Seth Robertson Avatar answered Nov 15 '22 08:11

Seth Robertson