What is the time complexity of permutations?

Question

I want to just say that it's time O(n) and space complexity is O(n!), but I am not certain. Can anyone confirm this or tell me what it is?

https://docs.python.org/2/library/itertools.html#itertools.permutations

Answer 1

Note: I haven't actually looked at the code involved, so I suppose this isn't quite certain; this does, however, reflect how I'd implement this.

The iterable makes a copy of the input and sorts it. It then generates permutations as they're asked for--i.e., it's not generating all the permutations, storing them,then iterating over a collection. Rather, it's generating each permutation on the fly, as it's required.

As such, you pretty much have the complexities backwards. At any given time, there's only one copy of the input, so space complexity is O(N). You can iterate over N! permutations, so time complexity to complete the iteration is O(N!).