<p>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.</p>

<p>Given <span class="math-container">$n$</span> inputs numbered <span class="math-container">$1 ... n$</span>, there are <span class="math-container">$n!$</span> ordered permutations. I wish to reason about the time complexity of programs which generate a single such combination.</p>

<p>Clearly, the simplest program will be <code>f(x): x</code>, with <span class="math-container">$O(1)$</span>. If I write down all programs for a given problem size <span class="math-container">$n$</span> in the most efficient way, what will be the lower bound time complexity for the one with most operations?</p>

<p>A trivial solution is a <code>switch</code> statement of length <span class="math-container">$n$</span>, with <span class="math-container">$O(n)$</span>, but this is clearly not the most efficient way. Is there theory to answer this question?</p>

CC BY-SA 4.0
2019-06-20T00:55:10.663Z
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
CC BY-SA 4.0
2019-06-20T11:33:20.887Z
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
CC BY-SA 4.0
2019-06-20T14:00:10.943Z
Ah, it wasn't clear to me you meant time complexity. The counting argument is only for program size.
Joshua Grochow
CC BY-SA 4.0
2019-06-21T07:34:30.340Z
I've clarified that the question is about time complexity
MrMartin
CC BY-SA 4.0
2019-06-21T14:24:07.427Z
Using binary search in a lookup table, you can implement any permutation by an algorithm with running time $O(\log n)$.
Emil Jeřábek
CC BY-SA 4.0
2019-06-23T19:18:11.880Z
Thanks @EmilJeřábek, but is there a way to prove a minimum lower bound? The question isn't about a better algorithm, but about about the most efficient one.
MrMartin
CC BY-SA 4.0
2019-06-24T12:23:54.447Z
In the standard computation model of multi-tape Turing machines, $\Omega(\log n)$ is also a lower bound, as this is the bit-length of both the input and the output. Since you claim to be able to compute the identity permutation in $O(1)$ time, you presumably use a different computation model, which you however did not specify, which makes the question unanswerable.
Emil Jeřábek
<co.combinatorics><lower-bounds>
Lower bound for permutation generator
MrMartin
# Lower bound for permutation generator

(Asked by: username_0 on 2019-06-19)

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?

**Tags:** co.combinatorics, lower-bounds
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: Ah, it wasn't clear to me you meant time complexity. The counting argument is only for program size.  
> **username_0**: I've clarified that the question is about time complexity  
> **username_2**: Using binary search in a lookup table, you can implement any permutation by an algorithm with running time $O(\log n)$.  
> **username_0**: Thanks @EmilJeřábek, but is there a way to prove a minimum lower bound? The question isn't about a better algorithm, but about about the most efficient one.  
> **username_2**: In the standard computation model of multi-tape Turing machines, $\Omega(\log n)$ is also a lower bound, as this is the bit-length of both the input and the output. Since you claim to be able to compute the identity permutation in $O(1)$ time, you presumably use a different computation model, which you however did not specify, which makes the question unanswerable.  

---

## 0 answers

