Time complexity of Permutations


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


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!)


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.