current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote -2 down vote favorite
1

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

share|improve this question
2  
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
1  
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
4  
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
show 2 more comments

1 Answer

up vote 1 down vote

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)$).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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