nikel - 6 months ago 53

Java Question

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(n^{2}) + (1 + ... + O(n!) + O((n + 1)!) ) = O((n + 1)!)