Reputation: 1305
The time complexity of this algorithm to compute permutations recursively should be O(n!*n)
, but I am not 100% sure about the space complexity.
There are n
recursions, and the biggest space required for a recursion is n
(space of every permutation * n!
(number of permutations). Is the space complexity of the algorithm` O(n!*n^2)?
static List<String> permutations(String word) {
if (word.length() == 1)
return Arrays.asList(word);
String firstCharacter = word.substring(0, 1);
String rest = word.substring(1);
List<String> permutationsOfRest = permutations(rest);
List<String> permutations = new ArrayList<String>(); //or hashset if I don’t want duplicates
for (String permutationOfRest : permutationsOfRest) {
for (int i = 0; i <= permutationOfRest.length(); i++) {
permutations.add(permutationOfRest.substring(0, i) + firstCharacter + permutationOfRest.substring(i));
}
}
return permutations;
}
Upvotes: 0
Views: 2260
Reputation: 183612
No, the space complexity is "just" O(n! × n), since you don't simultaneously hold onto all recursive calls' permutationsOfRest
/ permutations
. (You do have two at a time, but that's just a constant factor, so isn't relevant to the asymptotic complexity.)
Note that if you don't actually need a List<String>
, it might be better to wrap things up as a custom Iterator<String>
implementation, so that you don't need to keep all permutations in memory at once, and don't need to pre-calculate all permutations before you start doing anything with any of them. (Of course, that's a bit trickier to implement, so it's not worth it if the major use of the Iterator<String>
will just be to pre-populate a List<String>
anyway.)
Upvotes: 1