python - Time complexity of recursive permutation printer -

while trying explain recursive algorithms generate permutations in lexicographic order, provided simple algorithm:

def permute(done, remaining):   if not remaining:     print done     return    sorted_rem = sorted(remaining)   l = len(sorted_rem)    in xrange(0, l):     c = sorted_rem[i]      # move c done portion.     done.append(c)     remaining.remove(c)      # permute remaining     permute(done, remaining)      # put c back.     remaining.append(c)     # remove done.     del done[-1]  def main():   permute([], [1,2,3,4])  if __name__ == "__main__":   main() 

first question: seems bit wasteful me , wonder time complexity has, given pythonic implementation this?

note optimal time complexity o(n * n!), need print n! permutations of size n.

i guessing because of sorted (which presume o(n log n) in python), additional log n factor added (which suppose practically negligible n can use program for).

the second part of question optimize bit.

second question: assuming can implement sorted in o(n) time, , append, remove , del[-1] in o(1) time, resulting time complexity?

i believe there proof runtime indeed o(n*n!).

(inspired earlier question here: complexity of recursive string permutation function)

we have following recursion time spent, without printing:

t(n) = n*t(n-1) + o(n^2)

now if u(n) = t(n)/n! must have that

u(n) = u(n-1) + o(n^2/n!)

this telescoping series.

thus get

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

using power series e^x, multiply differentiate x couple of times, see 2^2/2! + 3^2/3! + ... + n^2/n! = o(1)

thus

t(n) = o(n!).

this time spent without printing.

thus total time printing o(n * n!).

this proves not matter running time of sorted etc are, long polynomial, algorithm asymptotically optimal.

the constant bad, , matter when dealing n*n!.