c - What's the order of this algorithm in Big-O notation (string permutations)?

Question

What is the performance in Big-O notation of the following algorithm? It's a function I wrote to print all permutations of a string. I know for an input of length n there are n! different permutations. Can somebody provide an explanation of the analysis made to reach such conclusions?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void permute(char* output, char* input, int used[], int index, int length){
    int i;

    if (index == length) {
        printf("%s\n", output);
        return;
    }

    for (i=0; i< length; i++){
        if (! used[i] ){
            output[index] = input[i];
            used[i] = 1;
            permute(output, input, used, index+1, length);
            used[i] = 0;
        }
    }
}


int main(){
    char input[] = "abcd";
    char* output;
    int length = strlen(input);
    int* used;

    // Allocate space for used array
    used = (int*) malloc (sizeof (int)* length);
    memset (used, 0, sizeof (int)* length);

    // Allocate output buffer
    output = (char*) malloc ( length+1);
    if (!output) return 1;
    output[length] = '\0';

    // First recursive call
    permute(output, input, used, 0, length);

    free (output);

    return 0;
}

Answer 1

我知道对于长度为 n 的输入有 n！不同的排列。

你刚刚回答了你自己的问题

Answer 2

我会说 O(n!)，因为每个递归都会执行一个 n 轮循环，并在“大小”n-1 的对象上调用一些东西（因为 used[i] 已经掩盖了一个字符）。