Time complexity of recursive permutation printer

While trying to explain recursive algorithms to generate permutations in lexicographic order, I provided this simple algorithm:

def permute(done, remaining):
  if not remaining:
    print done
    return

  sorted_rem = sorted(remaining)
  l = len(sorted_rem)

  for i in xrange(0, l):
    c = sorted_rem[i]

    # Move to c to done portion.
    done.append(c)
    remaining.remove(c)

    # Permute the remaining
    permute(done, remaining)

    # Put c back.
    remaining.append(c)
    # Remove from done.
    del done[-1]

def main():
  permute([], [1,2,3,4])

if __name__ == "__main__":
  main()

First question: It seems a bit wasteful to me and I wonder what the time complexity it really has, given a pythonic implementation like this?

Note that the optimal time complexity will be O(n * n!), as we need to print n! permutations of size n.

I am guessing because of the sorted (which I presume is O(n log n) in python), an additional log n factor will be added (which I suppose is practically negligible for the n we can use this program for).

The second part of the question is to optimize it a bit.

Second question: Assuming that we can implement sorted in O(n) time, and append, remove and del[-1] in O(1) time, what would be the resulting time complexity?

I believe there is a proof that the runtime is indeed O(n*n!).

(Inspired by an earlier SO question here: complexity of recursive string permutation function)

We have the following recursion for the time spent, without printing:

T(n) = n*T(n-1) + O(n^2)

Now if U(n) = T(n)/n! then we must have that

U(n) = U(n-1) + O(n^2/n!)

This is a telescoping series.

Thus we get

U(n) = U(1) + 2^2/2! + 3^2/3! + ... + n^2/n!

Using the power series for e^x, multiply differentiate by x a couple of times, we see that 2^2/2! + 3^2/3! + ... + n^2/n! = O(1)

Thus

T(n) = O(n!).

This is the time spent without printing.

Thus the total time with printing is O(n * n!).

This also proves that it does not matter what the running time of sorted etc are, as long as they are polynomial, this algorithm will be asymptotically optimal.

The constant will probably be bad, and that is what would actually matter when dealing with n*n!.