Counting all permutations of a string (Cracking the Coding Interview, Chapter VI - Example 12)

Question

In Gayle Laakman's book "Cracking the Coding Interview", chapter VI (Big O), example 12, the problem states that given the following Java code for computing a string's permutations, it is required to compute the code's complexity

public static void permutation(String str) {
    permutation(str, "");
}

public static 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));
        }
    }
}

The book assumes that since there will be n! permutations, if we consider each of the permutations to be a leaf in the call tree, where each of the leaves is attached to a path of length n, then there will be no more that n*n! nodes in the tree (i.e.: the number of calls is no more than n*n!).

But shouldn't the number of nodes be:

since the number of calls is equivalent to the number of nodes (take a look at the figure in the video Permutations Of String | Code Tutorial by Quinston Pimenta).

If we follow this method, the number of nodes will be 1 (for the first level/root of the tree) + 3 (for the second level) + 3*2 (for the third level) + 3*2*1 (for the fourth/bottom level)

i.e.: the number of nodes = 3!/3! + 3!/2! + 3!/1! + 3!/0! = 16

However, according to the aforementioned method, the number of nodes will be 3*3! = 18

Shouldn't we count shared nodes in the tree as one node, since they express one function call?

Answer 1

You're right about the number of nodes. That formula gives the exact number, but the method in the book counts some multiple times.

Your sum also seems to be approach e * n! for large n, so can be simplified to O(n!).

It's still technically correct to say the number of calls is no more than n * n!, as this is a valid upper bound. Depending on how this is used, this can be fine, and may be easier prove.

For the time complexity, we need to multiply by the average work done for each node.

First, check the String concatenation. Each iteration creates 2 new Strings to pass to the next node. The length of one String increases by 1, and the length of the other decreases by 1, but the total length is always n, giving a time complexity of O(n) for each iteration.

The number of iterations varies for each level, so we can't just multiply by n. Instead look at the total number of iterations for the whole tree, and get the average for each node. With n = 3:

• The 1 node in the first level iterates 3 times: 1 * 3 = 3
• The 3 nodes in the second level iterate 2 times: 3 * 2 = 6
• The 6 nodes in the third level iterate 1 time: 6 * 1 = 6

The total number of iterations is: 3 + 6 + 6 = 15. This is about the same as number of nodes in the tree. So the average number of iterations for each node is constant.

In total, we have O(n!) iterations that each do O(n) work giving a total time complexity of O(n * n!).