CODEWITHSUNDEEP
algorithmrecursiontime-complexitycomplexity-theory
Manan Shori
Manan Shori

Reputation: 11

What is the tractability of the problem of traversing all the permutations of a set?

I wanted to implement a recursive algorithm to imitate nested for loops but with a count determined at run-time. For it I have to write a recursive algorithm that traverses all the permutations of a set.

I was curious about its tractability. I think that since permutations involve factorial function, the problem should be NP-Hard. I still want your insights about this problem.

Upvotes: 1

Views: 53

Answers (1)

John Kugelman
John Kugelman

Reputation: 361645

Iterating over all permutations is O(n!) which is about as bad as it gets. It's worse than polynomial, worse even than exponential. It's not even NP-hard, it's worse! Mathematically,

  • O(nc) ⊂ O(cn) ⊂ O(n!).

Or, in English,

  • polynomial < exponential < factorial.

For a problem to be NP its solution must be verifiable in polynomial time. The set of all permutations is of size n! ∈ O(n!) and cannot possibly be verified in polynomial time as verification requires one to iterate over the entire list.

To put it in perspective how bad this is, O(n!) is the complexity class of bogosort, a sorting algorithm where you sort a deck of cards by shuffling it and seeing if you got lucky.

Upvotes: 3

Related Questions