The time and space needed to generate all permutations of n elements is directly proportional to the number of permutations generated. Given an arbitrary permutation p of n elements, there could be one of n elements in p's first position, n - 1 elements in p's second position, and so on. From this, there is a total of n(n - 1)...(2)1 = n! permutations.
(Ab)using Stirling's approximation, n! = O(nn), which is far worse behavior than the exponential 2n.
This page last modified on 18 March 2004.