nikel nikel - 15 days ago 10
Java Question

Complexity for generating permutations of a string

I am trying to figure out how the complexity of a code(from Cracking the Coding Interview book) for generating all the permutations of a given string is O(n!).

I know that that's the best possible complexity as we have n! permutations but I would like to understand it codewise, because not every algorithm that does this would be O(n!).

The Code :

import java.util.*;

public class QuestionA {

public static ArrayList<String> getPerms(String str) {
if (str == null) {
return null;
}
ArrayList<String> permutations = new ArrayList<String>();
if (str.length() == 0) { // base case
permutations.add("");
return permutations;
}

char first = str.charAt(0); // get the first character
String remainder = str.substring(1); // remove the first character
ArrayList<String> words = getPerms(remainder);
for (String word : words) {
for (int j = 0; j <= word.length(); j++) {
String s = insertCharAt(word, first, j);
permutations.add(s);
}
}
return permutations;
}

public static String insertCharAt(String word, char c, int i) {
String start = word.substring(0, i);
String end = word.substring(i);
return start + c + end;
}

public static void main(String[] args) {
ArrayList<String> list = getPerms("abcde");
System.out.println("There are " + list.size() + " permutations.");
for (String s : list) {
System.out.println(s);
}
}

}


This is what I have thought untill now :
At any function call , the number of words available is (n-1) ; assuming we are at a place where remainder is of length (n-1). Now to insert the nth element in all possible places for all of these (n-1) words takes (n-1)*(n-1) time.

so across the execution , it should be (n-1)^2+(n-2)^2+(n-3)^2+....2^2+1^2 operations, which I don't think is n!.

What did I miss here?

Answer

I think the time complexity of getPerms is O((n + 1)!).

We denote the running time of getPerms by T(n), where n is the length of the input.

===================================================================

The two if branches and the line char first = str.charAt(0) takes O(1) time. And the following line takes O(n) time:

String remainder = str.substring(1); // remove the first character

the next line takes time T(n - 1):

ArrayList<String> words = getPerms(remainder);

Now we consider the running time of the nested for-loops. The size of the outer for-loop is (n-1)!:

for (String word : words) {

and the size of the inner for-loop is n + 1:

for (int j = 0; j <= word.length(); j++) {

and the complexity of insertCharAt is also O(n).

So the total running time of the nested for-loops is (n + 1) * (n - 1)! * O(n) = O((n + 1)!).

Therefore we have the following relationship:

T(n) = T(n - 1) + O(n) + O((n + 1)!)
     = T(n - 1) + O(n) + O((n + 1)!)
     = (T(n - 2) + O(n - 1) + O(n!) + O(n) + O((n + 1)!)
     = T(n - 2) + ( O(n - 1) + O(n) ) + ( O(n!) + O((n + 1)!) )
     = ...
     = O(n2) + (1 + ... + O(n!) + O((n + 1)!) )
     = O((n + 1)!)