Big O notation of string permutation in Python

Question

def permutation(str): #str = string input

    if len(str) == 0:

        return [""]

    result = []

    for i, char in enumerate(str):

        for p in permutation(str[:i] + str[i + 1 :]):

            result.append(char + p)

    return result

I am confused in asymptotic analysis (time complexity) in this code does it have an O(n!) or O(n*n!) because the recursive call is in the loop. I am still confused does the big O notation only based on regular notation like logarithmic, linear, quadratic, exponential, factorial, etc. Or could beyond that like a combination not only based on the regular notation

I already tried to calculate it and see some explanation in youtube but still couldn't understand well.

Answer 1

Let the time complexity of the function be T(n), where n is the length of the input string.

For the case where n is not 0, we need to consider the following parts:

1. For the outer loop, it needs to be repeated n times.

2. For the outer loop body, the time complexity of each recursive call is T(n - 1). (I omitted the O(n) time complexity of constructing the input, considering that T(n - 1) is at least (n - 1)!, which should not affect the results.)

3. For inner loop, since the output size of the permutation is n!, it needs to be repeated (n - 1)! times (the input length for recursive calls is n - 1).

4. For the inner loop body, due to the length of p being n - 1, the time complexity of char + p is O(n).

In summary, we can conclude that:

T(n) = n * (T(n - 1) + O(n) * (n - 1)!)
     = n * T(n - 1) + n * O(n!)
     = n * ((n - 1) * T(n - 2) + (n - 1) * O((n - 1)!)) + n * O(n!)
     = n * (n - 1) * T(n - 2) + (n - 1) * O(n!) + n * O(n!)
     ...
     = n! * T(0) + 1 * O(n!) + 2 * O(n!) + ... + n * O(n!)
     = O(n!) + (1 + 2 + ... + n) * O(n!)
     = O((1/2 * n**2 + 1/2 * n + 1) * n!)
     = O(n**2 * n!)