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