next_permutation time complexity in big O notation

user_8678792 0
Viewed 8205

As far as I can tell, std::next_permutation algorithm runs in O(n!) time. Can anyone explain why that is? Or if I am even right about it?

Here is the code I am running it in, trying to count the number of permutations until the given array, of size n, has been sorted:

int permutationSort(int a[], int n)
   {
      int count = 0;

      while (next_permutation(a, a + n))
      {
          count++;
      }

      return count;
   }
algorithm c++
2 Answers

The complexity of std::next_permutation that transforms the permutation to the next permutation in the lexicographic order is O(n) in the worst case.

The number of permutations of n distinct elements is n!. The number of permutations of multisets is n!/(n1!*n2!*...*nk!) where ni is the number of equal elements of type i.

We have two different cases:

  1. Distinct numbers (set).

    next_permutation is often (if not always) implemented with O(1) amortized time when all elements are distinct. The latter means that next_permutation will have O(1) average time when calling many times consequently.

    In this scenario, the complexity of your permutationSort function is O(n!) in the worst-case scenario because of n! loop iterations with the amortized O(1) call of next_permutation.

  2. Numbers with repetitions (multiset)

    In this case, next_permutation has no guaranteed O(1) amortized complexity, but the number of 'permutations of multiset' could be much less than n!. The upper bound of the permutationSort function complexity is O(n!*n) in the worst case. I suppose it can be reduced to O(n!) but don't know how to prove this fact.

user_47592000

Your example isn't measuring anything about the workings of std::next_permutation. It is only measuring how many times you call it. You do have O(n!) calls to std::next_permutation.

You have to look at the reference to find the complexity of code that you don't have the source of. Alternatively you can construct a type that counts swaps and comparisons, to get an empirical measure of the complexity. That isn't an analysis, but it provides similar information.

user_26108100
Related