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?

Improve this question
$\endgroup$
5
  • 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$ Commented Aug 4, 2017 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$ Commented Aug 5, 2017 at 15:19
  • $\begingroup$ Edited. There was a problem in the markup $\endgroup$ Commented Aug 5, 2017 at 21:15
  • 1
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ Commented Aug 5, 2017 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$ Commented Aug 5, 2017 at 21:37

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.