Time complexity of Permutations


#1

I think the time complexity here is O(n2). Can someone please clarify, or state if they have different opinion


#2

The number of elements your are calculating will give you the lower bound which is n! >> n^2.

quora: What is the fastest algorithm to find all possible permutations of a string?

tldr: O(n*n!)


#3

If you use Heap’s algorithm the time complexity is O(n!).

Of course, O(n!) holds only if you do not store/use the majority of the permutations.