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.
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)
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With