¿Cuál es el tiempo de ejecución de este algoritmo powerset

Question

tengo un algoritmo para calcular la powerset de un conjunto utilizando todos los bits entre 0 y 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); 
     } 

    } 

Mi pregunta es: ¿Cuál es la ejecución tiempo de este algoritmo El ciclo se ejecuta 2^n veces y en cada iteración el ciclo while ejecuta lg (i) veces. Así que creo que el tiempo de ejecución es

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

Pero no sé cómo simplificar esto más, sé que esto puede resolverse en O (n^2) tiempo (no espacio) de forma recursiva, por lo que Me pregunto si el método anterior es mejor o peor que esto, en el tiempo ya que es mejor en el espacio.

Answer 1

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 

por lo tanto, la solución sugerida es de valor en términos de tiempo de complejidad a continuación, el O recursiva (2^n) uno.

---

EDIT:
Para ser exactos, sabemos que para cada k-log(k!) está en Theta(klogk), por tanto, para k=2^n tenemos que lg((2^n)!) está en Theta(2^nlog(2^n) = Theta(n*2^n)

Answer 2

Sin tratar de resolver o simular, es fácil ver que esto es peor que O (2^n) porque este es 2^n * $ valor donde $ valor es mayor que uno (para todo i> 2) y aumenta a medida que n aumenta, por lo que obviamente no es una constante.

Answer 3

Al aplicar la fórmula de Sterling, en realidad es O (n * 2^n).