The tricky time complexity of the permutation generator 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.

In the analysis of algorithms there are different 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.
