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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Jun 20 '19 at 0:55
  • $\begingroup$ 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? $\endgroup$ – MrMartin Jun 20 '19 at 11:33
  • $\begingroup$ Ah, it wasn't clear to me you meant time complexity. The counting argument is only for program size. $\endgroup$ – Joshua Grochow Jun 20 '19 at 14:00
  • $\begingroup$ I've clarified that the question is about time complexity $\endgroup$ – MrMartin Jun 21 '19 at 7:34
  • $\begingroup$ Using binary search in a lookup table, you can implement any permutation by an algorithm with running time $O(\log n)$. $\endgroup$ – Emil Jeřábek Jun 21 '19 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.