I ran into tricky issues in computing time complexity of the permutation generator algorithm, and had great difficulty convincing a friend (experienced in Theoretical CS) of the validity of my reasoning. I'd like to clarify this here.
Tricky complexity question Given a positive integer $n$, what is the time complexity of generating all permutations on the set $[n]=\{1,2,..,n\}$?
Friend's reasoning Any algorithm to generate all permutations of $[n]$ takes $\Omega(n!)$ time. This is a provable , super-exponential lower bound, [edited ]hence the problem is in EXPTIME.
My reasoning The above reasoning is correct, except that one should compute the complexity with respect to the number of expected output bits. Here, we expect $n!$ numbers in the output, and each can be encoded in $\log n$ bits; hence we expect $b=O(n!\log n)$ output bits. A standard algorithm to traverse all $n!$ permutations will take a polynomial time overhead i.e. it will execute in $s(n)=O(n!n^k)$ time, hence we will need $t(n)=b(n)+s(n) = O(n!(\log n + n^k)) $ time in all.
Since $b(n)$ is the number of output bits, we will express $t(n)$ as a function of $b(n)$. To do so, note that $n^k \approx (n!)^{k/n}$ using $n! \approx n^n$; so $s(n)=O( b(n) (b(n))^{k/n}) = O(b^2(n) )$ . Hence we have a polynomial time algorithm in the number of output bits, and the problem should be in $P$, not in say EXPTIME.
Main Question : Whose reasoning is correct, if at all?
Note I raised this problem here because I had a bad experience at StackOverflow with a different tricky time complexity problem; and this is certainly not suited for Cstheory.SE as it isn't research level.
Best Answer
When classifying problems, they are not classified according to the size of the output, in bits, but rather, the size of the input. The size of the input is the size of the problem, which is the size we care about when defining standard complexity classes. Problems in P take time bounded by a polynomial function of the problem size. Problems in P-SPACE take space bounded by a polynomial function of the problem size. Problems in E take time bounded by an exponential function of the problem size, and so on. If the size of the output is exponential in the size of the input problem, (which, in this case would be the initial set), then it's clear that the problem must be, at minimum, exponential.
If you wish to define your own classification of problems (POUT-TIME and POUT-SPACE or something) in terms of the size of the output, you are welcome to, but this is not how standard complexity classes are defined. Your friend is correct.