Powerset generation using recursion and time complexity

Question

I have a program that generates power set of a given string, the set being the characters of the string.

public static Set subsets(String s) {
    Set subsets = new HashSet();
    if (s.length() == 0) {
        subsets.add("");
    } else if (s.length() == 1) {
        subsets.add("");
        subsets.add(s);
    } else {
        for (int i = 0; i < s.length() - 1; i++) {
            Set sets = subsets(s.substring(i + 1));
            for (String st : sets) {
                subsets.add(s.substring(0, 1) + st);
            }
            subsets.addAll(sets);
        }
    }
    return subsets;
}

I don't seem to understand how to calculate time complexity of the above implementation.I understand that String.substring and creating Set Objects are pretty expensive, but if I assume these two operations to take constant time, what would be the overall time complexity?

Answer 1

You should have converted you Java code into pseudo code.

In fact, if your code runs exactly as you describe, namely given a set $S$ as a string it generate all subsets of the symbols of the input string, then the running time is trivial. You just need to count the number of different subsets generated by your algorithm/code. Input size is the length of the input string, i.e., number of characters. So, if the number of characters is $n$ then there are total $2^n$ different subsets. So, the time complexity is $O(2^n)$.