Geek Answers Handbook

What is the running time of this power algorithm

I have an algorithm to compute a force set set using all 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 runs 2 ^ n times, and at each iteration, the while loop starts lg (i) times. Therefore, I think work time

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 that it can be solved in O (2 ^ n) time (and not in space) recursively, so I wonder if the method is better or worse, since it is better in space .

+5
source share
3 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

therefore, the proposed solution stands in terms of time complexity, and then recursive O (2 ^ n).

EDIT: , , k - log(k!) Theta(klogk), k=2^n , lg((2^n)!) Theta(2^nlog(2^n) = Theta(n*2^n)

+6

, , , O (2 ^ n), 2 ^ n * $, $ ( i > 2) n, , , .

+2

Applying the Sterling formula, it is actually O (n * 2 ^ n).

+2
source

More articles:


All Articles