Question: 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.

Answer: 
I wish to substantially refine Keith Irwin's answer as follows.

Given a class of problems $\mathcal{P}$, the solution to each of which can be computed in polynomial time in the size of their inputs. This does *not* mean that $\mathcal{P}$ lies in the complexity class $\mathsf{P}$. Why not? Because $\mathsf{P}$ admits *only* decision problems !

For example, suppose $\mathcal{P}$ is that class of problems that provides as input a positive integer $n$ and asks the value of $n+1$ as output. It's easy to see that $\mathcal{P}$ can be solved in polynomial time in input size. But $\mathcal{P} \not \subset \mathsf{P}$, for $\mathcal{P}$ does not consist of decision problems at all! Instead $\mathcal{P}$ is a set of [function problems](http://en.wikipedia.org/wiki/Function_problem); it lies in $\mathsf{FP}$, that class of functions computable in poly time. 

Similarly, the permutation generator takes input $n$ and provides a function $f(n)$ as output; it does not *decide* anything. Hence, regardless of its complexity, it does not belong in $\mathsf{P}$. It's more meaningful to think of the permutation generation problem as a function problem. The provable super exponential bound mentioned in the question prevents the generation problem from lying in $\mathsf{FP}$. Perhaps $\mathsf{FEXP}$ would be a better answer, though I'm not sure. As Keith said,using the number of output bits as a measure of complexity needs new definitions of complexity classes that take output size into question. 

Note that it's certainly meaningful to make *decision versions* of the permutation generation problem, such as: 

> 
> Given integers $(n,k)$, what is the $k$-th bit of the output of the permutation generator on $[n]$? 
> 
> 
> 

This particular problem is indeed in $\mathsf{P}$, for the $k$th bit can be computed by efficient [permutation unranking](http://ldc.usb.ve/~bonet/reports/AAAI08-ws10-ranking.pdf).
In the analysis of algorithms there are different [cost models](http://en.wikipedia.org/wiki/Analysis_of_algorithms#Cost_models).

The most common ones are (quote from Wikipedia):

> 
> * the uniform cost model, also called uniform-cost measurement (and similar variations), assigns a constant cost to every machine
> operation, regardless of the size of the numbers involved
> * the logarithmic cost model, also called logarithmic-cost measurement (and variations thereof), assigns a cost to every
> machine operation proportional to the number of bits involved
> 
> 
> 

I guess the complexities you gave use a different model and therefore can not be compared, they can both be correct.