Time Complexity of String Permutations

Question

I'm currently reading Cracking the Coding Interview by Gayle Laakmann McDowell and I'm having trouble understanding one of the examples in the book.

Im on the chapter about time complexity, and for example 12 on page 51, the book gives an example code that counts all permutations of a string.

The time complexity is described as O(n^2 * n!). Despite there being a detailed explanation in the book, I'm having a hard time understanding the logic.

Here is the code,

void permutation(String str) {
    permutation (str, “”) ;
}

void permutation (String str, String prefix) {
    if (str.length() == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

I tried finding the time complexity on my own, but I evaluated it as O(n * n!) not O(n^2 * n!).

I'll include my logic below.

Using the example of initial call permuation(“hello”, “”), I know the for loop will have 5 iterations on the first call. Each iteration will have a recursive call to permutation(): permuation(“ello”, “h”), permutation(“hllo”, “e”), permutation(“helo”, “l”), permutation(“helo”, “l”), and permuation(“hell”, “o”).

Then, for each of the next calls we have 4 recursive calls. For each of those next calls, we have 3 recursive calls. For each of those next calls, we have 2 recursive calls. For each of those next calls, we have 1 recursive call.

So, there are n * (n-1) * … * 2 * 1 = n! calls to permutation(). permutation() has O(n) for each call. Thus, O(n! * n).

Please let me know if you see where I wen't wrong, or just any insight into why the time complexity is O(n^2 * n!) not O(n * n!). Thank you!!!

Answer 1

You are missing that the line String rem = str.substring(0, i) + str.substring(i + 1); has to construct a new string of length up to O(n), which therefore takes time O(n). Therefore each of n! permutations requires n calls to functions that take time proportional to n each. Leading to O(n^2 n!).