Considere o seguinte código.

public class Permutations {
    static int count=0;
    static void permutations(String str, String prefix){
        if(str.length()==0){
            System.out.println(prefix);
        }
        else{
            for(int i=0;i<str.length();i++){
                count++;
                String rem = str.substring(0,i) + str.substring(i+1);
                permutations(rem, prefix+str.charAt(i));
            }
        }

    }
    public static void main(String[] args) {
        permutations("abc", "");
        System.out.println(count);
    }

}

aqui a lógica que eu acho que é seguida é: ela considera cada caractere da string como um prefixo possível e permite os caracteres n-1 restantes.
portanto, por essa relação de recorrência lógica acaba sendo

T(n) = n( c1 + T(n-1) )          // ignoring the print time

que é obviamente O (n!). mas quando usei uma variável count para ver quando algo realmente cresce na ordem de n !, encontrei resultados diferentes.
para string de 2 comprimentos para count ++ (dentro do loop) é executado 4 vezes, para string de 3 comprimentos o valor de count vem 15 e para strings de 4 e 5 comprimentos são 64 e 325.
Isso significa que cresce pior que n !. então por que se diz que isso (e algos semelhantes que geram permuatações) são O (n!) em termos de tempo de execução.