Understanding Example 12 All Permutations of a string from Big O notation - Cracking the Coding Interview

Question

I'm stuck understanding how the author got the complexity of O(n^2 * n!) of the following procedure which generates all permutation of a string.

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

Answer 1

The complexity of the method is O(n^2 *n!) because of the else path cost:

First notice that each call to String rem=str.substring(0,i)+str.substring(i+1); is O(n), in the else path we compute it n times together with a call to permutation which has complexity T(n-1).

Computing the complexity of this is equivalent to solving: T(n) = n[n+T(n-1)]; n times (the for loop) a work of (n+T(n-1))

Solving this recurrence is not that easy, If I'm not wrong it should boil down to solving:

But let's try to approximate. Each permutation (base case) represent a node in the recursion tree. This tree has n! leaf. Each leaf has a path to the root of length n. So It is safe to assume there are not more than n*n! nodes in the tree.

This is an upper bound on the number of calls to permutation. Since each of this call costs n then the overall upper bound on the complexity is O(n^2*n!)

Hope this helps.

Answer 2

I'm late to the party but nonetheless I will still post my answer.

This is how I explained it to myself. Taking a simplified approach, lets ignore all the steps of the function: permutation(String str, String prefix) except the recursive step.

Keeping above in mind, the time complexity of the function can be stated in terms of recurrence relation: T(N) = N*T(N-1), where N is the length of the input string. Upon expansion, T(N) = N*(N-1)*(N-2)*...3*2*1*T(0). --- (*)

Now, T(0) = O(N) because in base case we are printing the prefix string, and printing a string of length N is an O(N) operation.

Expressing (*) above in closed form: N*N! --- (1)

Now consider the following line of thepermutation function: String rem = str.substring(0, i) + str.substring(i + 1);

This is again O(N) operation and this is done for each of the N! recursive calls. Therefore considering above and taking product with the expression (1) above, the total runtime complexity T(N) turns out to be

N*N*N! = N^2*N!

Answer 3

A simple trick to solve this one is O(number of nodes * computation in each node).

computation in each node is O(n).

Number of nodes can be calculated by summing nodes at each level.

i.e. (n! / 1!) + (n! / 2!) + (n! / 3!) ... + (n! / n!)

which equals n! * (1/1! + 1/2! + ... + 1/n!)

The sum of this series (1/1! + 1/2! + ... + 1/n!) was considered as n (as an upper bound)

Which lead to make the number of nodes to be n * n!

So, O(number of nodes * computation in each node) is O( n * n! * n) which is O(n² * n!)

---

But, if we do real math, (1/1! + 1/2! + ... + 1/n!) is 1.7182 ( where n is > 6 )

So, the number of nodes are 1.7182 * n!. The complexity must be O(1.7182 * n! * n) which is O(n * n!)

---