educative.io

Space complexity of Permutations

Courses
,
#1

The solution reports a space complexity of O(n) because there are at most n stack frames active at once, where n is the length of the input string.

In each of the stack frames, on line 14, we create a new swapped_str that’s the same length as the original string, n, and remains until the frame closes.

With n frames each with a new string of length n, would our space complexity be O(n^2)? I think this approach would get us down to O(n) space:

def permute_word(word):
    def recurse(word, i):
        nonlocal result, n
        if i == n - 1:
            result.append("".join(word))
        for j in range(i, n):
            word[i], word[j] = word[j], word[i]
            recurse(word, i + 1)
            word[i], word[j] = word[j], word[i]
    result = []
    n = len(word)
    recurse(list(word), 0)
    return result

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Permutations

1 Like
#2

Hello again @Isaac_Haseley,

Thanks for bringing up your concerns regarding the space complexity of the algorithm. I get why you might initially think the space complexity could be O(n^2), given that for each of the n recursion stack frames, a new string of length n is created. However, the space complexity remains O(n), and here’s a simplified explanation:

For the recursion stack depth, the algorithm’s space complexity is mainly influenced by the recursion stack, which grows linearly with the input string’s length, n, in this problem which is 6. This is because the deepest the recursion goes is n levels deep, corresponding to the length of the string. And while it is true that a new string is created in each recursion frame, these strings do not contribute to a quadratic space complexity. Our point of focus here is that each created string is only relevant within its own recursive call and does not accumulate across calls. Therefore, the space required for these strings does not add up in a way that would result in O(n^2) complexity.

Therefore, the overall space complexity of the algorithm is O(n) because the space used by the recursion stack is the dominant factor, and it grows linearly with the size of the input. The creation and disposal of temporary strings within each recursive call do not change this overall analysis.

I’d also like to share a short feedback on the provided solution code. Yes, that is indeed another way to solve the permutations problem but it’s space complexity still remains the same as you mentioned, O(n). We’re really happy to see that our user’s are coming with interesting solutions. :smiley:

I hope this clarifies your concern! Please feel free to share further suggestions and feedback. We’d be happy to help. Thanks!

Happy learning!

#3

Hey @Dian_Us_Suqlain!

Our point of focus here is that each created string is only relevant within its own recursive call and does not accumulate across calls.

Say we have an input string of length 1000, and our algorithm is at its maximum depth of 1000 frames. Would we need to store 1000 strings of length 1000, so that when we exit each frame, the enclosing frame remembers its string?