Estou tentando descobrir a complexidade do tempo de uma função que escrevi (isso gera umaconjunto de força para uma determinada sequência):

public static HashSet<string> GeneratePowerSet(string input)
{
    HashSet<string> powerSet = new HashSet<string>();

    if (string.IsNullOrEmpty(input))
        return powerSet;

    int powSetSize = (int)Math.Pow(2.0, (double)input.Length);

    // Start at 1 to skip the empty string case
    for (int i = 1; i < powSetSize; i++)
    {
        string str = Convert.ToString(i, 2);
        string pset = str;
        for (int k = str.Length; k < input.Length; k++)
        {
            pset = "0" + pset;
        }

        string set = string.Empty;
        for (int j = 0; j < pset.Length; j++)
        {
            if (pset[j] == '1')
            {
                set = string.Concat(set, input[j].ToString());
            }
        }
        powerSet.Add(set);
    }
    return powerSet;
}

Então, minha tentativa é esta:

deixe o tamanho da string de entrada ser nno loop for externo, deve iterar 2 ^ n vezes (porque o tamanho definido é 2 ^ n).no loop for interno, devemos iterar 2 * n vezes (na pior das hipóteses).

1. Então Big-O seria O ((2 ^ n) * n) (já que descartamos a constante 2) ... isso está correto?

E n * (2 ^ n) é pior que n ^ 2.

se n = 4 então
(4 * (2 ^ 4)) = 64
(4 ^ 2) = 16

se n = 100 então
(10 * (2 ^ 10)) = 10240
(10 ^ 2) = 100

2. Existe uma maneira mais rápida de gerar um conjunto de potência, ou é ideal?