title: Time complexity of recursive permutation printer
body: <p>While trying to explain <a href="https://stackoverflow.com/a/29935145/4838497">recursive algorithms to generate permutations in lexicographic order</a>, I provided this simple algorithm:</p>
  
  <pre><code>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()
  </code></pre>
  
  <blockquote>
    <p>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?</p>
  </blockquote>
  
  <p>Note that the optimal time complexity will be <code>O(n * n!)</code>, as we need to print n! permutations of size n.</p>
  
  <p>I am guessing because of the sorted (which I presume is <code>O(n log n)</code> in python), an additional <code>log n</code> factor will be added (which I suppose is practically negligible for the <code>n</code> we can use this program for).</p>
  
  <p>The second part of the question is to optimize it a bit.</p>
  
  <blockquote>
    <p>Second question: Assuming that we can implement <code>sorted</code> in <code>O(n)</code> time, and <code>append</code>,
    <code>remove</code> and <code>del[-1]</code> in <code>O(1)</code> time, what would be the resulting time
    complexity?</p>
  </blockquote>