# Exponential input and poly-time algorithm

For a list of integers, of size n, where n is exponential, will merge-sort(n), run in poly-time or psuedo poly-time?

-
poly time, because your input is of siye $n$, because you have $n$ numbers, and each of them takes at least $O(1)$ space, also for checking more in detail (for furthor problems), you can see this related question: cs.stackexchange.com/questions/1643/… – user742 Nov 4 '12 at 20:25
@SaeedAmiri so for example, if we consider the subset sum problem, if we have a list on size n and integer k,if k = n, and there exist an algorithm that runs in O(nk), is that a polytime algorithm or exponential (with the possibility of n being exponential)? – Mike G Nov 4 '12 at 20:29
The running time of an algorithm is measured against the size of the input. When you say that $n$ is exponential, this means that the input has size logarithmic in $n$. This is the case if $n$ is the only input, but not the case if the input also contains an array of length $n$. – Yuval Filmus Nov 5 '12 at 1:17
Exponential in what? – Raphael Nov 5 '12 at 8:06
@MikeG, The algorithm you mentioned,if someone find it for subset sum!, is poly time, but if the $k$ is independent to the $n$ (like current available algorithms), it can be exponential, depend to size of $k$. because the input is $n$ different number and each of them may take $O(\log k)$ space, but running time is $O(n\cdot k)$, and you know there isn't any poly relation between $\log k$ and $k$. – user742 Nov 5 '12 at 8:26

First, the question is not well defined. If the input is of size $n$, the algorithm is measured with respect to $n$. However, the question suggests that $n$ is already exponential (in what?!)
Lets assume each number takes $k$ bits, and we have $n$ different numbers to sort, where $n$ is exponential in $k$.
Then, merge sort takes $O(n \log n)$ comparisons. Each comparison takes $O(\log k)$ time (unless we use some gates that compare two numbers in $O(1)$).