CODEWITHSUNDEEP
algorithmbig-opermutation
alessiop86
alessiop86

Reputation: 1305

What's the space complexity of this permutations algorithm?

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

Answers (1)

ruakh
ruakh

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

Related Questions