CODEWITHSUNDEEP
javastringtime-complexitybig-opermutation
Ahmed Ismail
Ahmed Ismail

Reputation: 113

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

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:

foo+bar

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?

Upvotes: 11

Views: 4897

Answers (2)

fgb
fgb

Reputation: 18559

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!).

Upvotes: 9

Lawliet
Lawliet

Reputation: 3499

According to your video where we have string with 3 characters (ABC), the number of permutations is 6 = 3!, and 6 happens to be equal to 1 + 2 + 3. However, if we have a string with 4 characters (ABCD), the number of permutations should be 4 * 3! as D could be in any position from 1 to 4. With each position of D you can generate 3! permutations for the rest. If you re-draw the tree and count the number of permutations you will see the difference.

According to your code, we have n! = str.length()! permutations, but in each call of the permutations, you also run a loop from 0 to n-1. Therefore, you have O(n * n!).

Update in response to the edited question

Firstly, in programming, we often have either 0->n-1 or 1->n not 0->n.

Secondly, we don't count the number of nodes in this case as if you take a look at the recursion tree in the clip again, you will see nodes duplicated. The permutations in this case should be the number of leaves which are unique among each other.

For instance, if you have a string with 4 characters, the number of leaves should be 4 * 3! = 24 and it would be the number of permutations. However, in your code snippet, you also have a 0->n-1 = 0->3 loop in each permutation, so you need to count the loops in. Thus, your code complexity in this case is O(n *n!) = O(4 * 4!).

Upvotes: 0

Related Questions