Generating all permutations of n distinct elements takes at least…
Options
- O(n), because each element is visited once
- O(n²), because each pair is compared
- O(n!) outputs, and O(n · n!) to write them (Correct option)
- O(2ⁿ), because each element is in or out
Answer
O(n!) outputs, O(n · n!) to write them
Why
There are n! orderings (3 items: 6; 10 items: 3,628,800), and each permutation has n elements to write out.
Such problems are solved with backtracking: choose an element, recurse on the rest, then undo the choice and try the next.
For comparison, the number of subsets is 2ⁿ.
Remember
Permutations = n!, subsets = 2ⁿ.