# Lower bound for permutation generator

I'm interested in a problem akin to combinatorial circuits, but in terms of complexity. Apologies for missing the correct terminology, I'll appreciate any corrections.

Given $$n$$ inputs numbered $$1 ... n$$, there are $$n!$$ ordered permutations. I wish to reason about the time complexity of programs which generate a single such combination.

Clearly, the simplest program will be f(x): x, with $$O(1)$$. If I write down all programs for a given problem size $$n$$ in the most efficient way, what will be the lower bound time complexity for the one with most operations?

A trivial solution is a switch statement of length $$n$$, with $$O(n)$$, but this is clearly not the most efficient way. Is there theory to answer this question?

• Your switch statement actually uses n log n because the return statement from each case is a number from 1 to n, which takes log n bits to write down. And this is the best you can do in the worst case, by a counting argument. (There are n! permutations, and the most you can describe in b bits is 2^b, so you need b at least log(n!) ~ n log n.) Nice question, but doesn't really seem to be research level (which is the purpose of this site), maybe better for CS.SE. – Joshua Grochow Jun 20 '19 at 0:55
• Thank you @JoshuaGrochow, and feel free to move the question to cs.se if you see fit. I don't have the rep. Regarding the counting argument, it shows that the program must have at least $n \times log(n)$ bits, but why should that relate to time complexity? – MrMartin Jun 20 '19 at 11:33
• Ah, it wasn't clear to me you meant time complexity. The counting argument is only for program size. – Joshua Grochow Jun 20 '19 at 14:00
• I've clarified that the question is about time complexity – MrMartin Jun 21 '19 at 7:34
• Using binary search in a lookup table, you can implement any permutation by an algorithm with running time $O(\log n)$. – Emil Jeřábek Jun 21 '19 at 14:24