0
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Can you please replace your code with pseudocode? I would also check here and here. What have you tried so far to analyze it? What specifically are you having trouble with? $\endgroup$ – ryan Aug 4 '17 at 21:12
  • $\begingroup$ It appears you have copied your code incorrectly, because of this line: for (int i = 0; i sets = subsets(s.substring(i + 1)); $\endgroup$ – Riley Aug 5 '17 at 15:19
  • $\begingroup$ Edited. There was a problem in the markup $\endgroup$ – Kumar Bibek Aug 5 '17 at 21:15
  • 1
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – David Richerby Aug 5 '17 at 21:31
  • 1
    $\begingroup$ Personally, I would take real code over pseudo-code any day of the week. Especially code written in a common language that isn't relying on any uncommon features or subtle details. $\endgroup$ – Derek Elkins Aug 5 '17 at 21:37
3
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.