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

  • 2
    $\begingroup$ 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/… $\endgroup$ – user742 Nov 4 '12 at 20:25
  • $\begingroup$ @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)? $\endgroup$ – Mike G Nov 4 '12 at 20:29
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Nov 5 '12 at 1:17
  • 4
    $\begingroup$ Exponential in what? $\endgroup$ – Raphael Nov 5 '12 at 8:06
  • $\begingroup$ @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$. $\endgroup$ – 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)$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.