I'm trying to figure out the time complexity of a function that I wrote (it generates a power set for a given string):

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

So my attempt is this:

• let the size of the input string be n
• in the outer for loop, must iterate 2^n times (because the set size is 2^n).
• in the inner for loop, we must iterate 2*n times (at worst).

1. So Big-O would be O((2^n)*n) (since we drop the constant 2)... is that correct?

And n*(2^n) is worse than n^2.

if n = 4 then
(4*(2^4)) = 64
(4^2) = 16

if n = 100 then
(10*(2^10)) = 10240
(10^2) = 100

2. Is there a faster way to generate a power set, or is this about optimal?