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?