Estoy tratando de averiguar la complejidad temporal de una función que escribí (genera unset de poder para una cadena dada):

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;
}

Entonces mi intento es este:

deje que el tamaño de la cadena de entrada sea nen el bucle for externo, debe iterar 2 ^ n veces (porque el tamaño establecido es 2 ^ n).en el bucle for interno, debemos iterar 2 * n veces (en el peor de los casos).

1. Entonces Big-O sería O ((2 ^ n) * n) (ya que eliminamos la constante 2) ... ¿es correcto?

Y n * (2 ^ n) es peor que n ^ 2.

si n = 4 entonces
(4 * (2 ^ 4)) = 64
(4 ^ 2) = 16

si n = 100 entonces
(10 * (2 ^ 10)) = 10240
(10 ^ 2) = 100

2. ¿Existe una forma más rápida de generar un conjunto de potencia, o se trata de lo óptimo?