Swap function time

Question

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

I do not understand how they calculated the runtime as O (n!). I assume that they mean that "n" is the length of the original string. I think the runtime 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 runtime of the outer and inner loops, respectively. Can someone explain to me why this is wrong / the answer to the book is right?

Thank.

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: Hacking Coding Interviews

Answer 1

, , N , , O (n!), n! .

, gePerm(n), n - n, getPerm(n-1). , , , N . ,

P _n= nP _n-1
P ₁= 1

, P _n= n! .

---

, , , .

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

N N * (N - 1) * (N - 2) * ... * 2 * 1, N!.

N. N - 1. N * (N - 1) .

, N * (N - 1) * (N - 2) * ....

N N!, , N , N!.