Running time of permutation function

Question

My book provides the following code for a function that computes all the permutations of a string of unique characters (see code below), and says that the running time is O(n!), "since there are n! permutations."

I don't understand how they've computed the running time as O(n!). I assume they mean "n" is the length of the original string. I think that the running time should be something like O((n + 1)XY), since the getPerms function will be called (n + 1) times, and X and Y can represent the running times of the outer and inner for loops respectively. Can someone explain to me why this is wrong / the book's answer is right?

Thanks.

public static ArrayList<String> getPerms(String str)
{
    if (str == null)
        return null;

    ArrayList<String> permutations = new ArrayList<String>();

    if (str.length() == 0)
        permutations.add("");
        return permutations;

    char first = str.charAt(0); //first character of string
    String remainder = str.substring(1); //remove first character

    ArrayList<String> words = getPerms(remainder);
    for (String word: words)
    {
        for (i = 0; i <= word.length(); i++)
        {
            String s = insertCharAt(word, first, i);
            permutations.add(s)
        }
    }

    return permutations;

}

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

Source: Cracking the Coding Interview

Answer 1

From our intuition, it is clear that there is no existing algorithm that generate permutation of N items that perform better than O(n!) because there are n! possibility.

You can reduce the recursive code into recurrence equation because gePerm(n) where n is a string with n length will call getPerm(n-1). Then, we use all the value returns by it and put a inner loop that loop N times. So we have

P_n = nP_n-1
P₁ = 1

It is easy to see that P_n = n! by telescoping the equation.

---

If you have hard times visualize how we come up with this equation, you can also think of this way

ArrayList<String> words = getPerms(remainder);
for (String word: words)                          // P(n-1)
{
    for (i = 0; i <= word.length(); i++)          // nP(n-1)
    {
        String s = insertCharAt(word, first, i);
        permutations.add(s)
    }
}

Answer 2

The count of permutations of N elements is N * (N - 1) * (N - 2) * ... * 2 * 1, i.e. N!.

First character can be any one of N characters. Next character can be one of remained N - 1 characters. Now we have N * (N - 1) possible cases already.

So, continuing we'll have N * (N - 1) * (N - 2) * ... cases at each step.

Cause the count of permutations of N elements is N!, then there isn't an implementation that can permutate an array of length N faster than N!.