Каково время работы этого алгоритма powerset

Question

У меня есть алгоритм для вычисления набора мощности набора, используя все биты от 0 до 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);
        }

    }

Мой вопрос: каково время работы этого алгоритма.Цикл выполняется 2 ^ n раз, и в каждой итерации цикл while выполняется lg (i) раз.Поэтому я думаю, что время выполнения составляет

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

Но я не знаю, как это еще больше упростить, я знаю, что это можно решить за O (2 ^ n) времени (нерекурсивно, поэтому мне интересно, лучше ли описанный выше метод, чем этот, с точки зрения времени и качества в пространстве.

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

Таким образом, предлагаемое решение стоит с точки зрения сложности времени, чем рекурсивное O (2 ^ n).

---

РЕДАКТИРОВАТЬ:
Кточнее, мы знаем, что для каждого k - log(k!) в Theta(klogk), таким образом, для k=2^n мы получаем, что lg((2^n)!) находится в Theta(2^nlog(2^n) = Theta(n*2^n)

Answer 2

Применяя формулу Стерлинга, на самом деле это O (n * 2 ^ n).

Answer 3

Не пытаясь решить или смоделировать, легко увидеть, что это хуже, чем O (2 ^ n), потому что это значение 2 ^ n * $, где значение $ больше единицы (для всех i> 2) и увеличивается при увеличении n, поэтому оно, очевидно, не является константой.