For a list of integers, of size n, where n is exponential, will merge-sort(n), run in poly-time or psuedo poly-time?
|show 2 more comments|
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)$).