nikel - 1 year ago 88
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 Source

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)!)
```
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download