Abstract | ||
---|---|---|
We study the fundamental problem of sorting in a sequential model of computation and in particular consider the time-space trade-off (product of time and space) for this problem.Beame has shown a lower bound of $\Omega(n^2)$ for this product leaving a gap of a logarithmic factor up to the previously best known upper bound of $O(n^2\log n)$ due to Frederickson. Since then, no progress has been made towards tightening this gap.The main contribution of this paper is a comparison based sorting algorithm which closes the gap by meeting the lower bound of Beame. The time-space product $O(n^2)$ upper bound holds for the full range of space bounds between $\log n$ and $n/\log n$. Hence in this range our algorithm is optimal for comparison based models as well as for the very powerful general models considered by Beame. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1109/SFCS.1998.743455 | FOCS |
Keywords | Field | DocType |
main contribution,logarithmic factor,time-space trade-off,powerful general model,optimal time-space trade-offs,full range,time-space product,fundamental problem,space bound,log n,sequential model,lower bound,trade off,computer science,chromium,upper bound,model of computation,computational complexity,power generation,sorting algorithm,sorting,time space,time measurement | Binary logarithm,Discrete mathematics,Combinatorics,Upper and lower bounds,Sorting,Omega,Logarithm,Mathematics,Sorting algorithm,Computation,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-8186-9172-7 | 29 |
PageRank | References | Authors |
1.66 | 15 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jakob Pagter | 1 | 194 | 9.68 |
Theis Rauhe | 2 | 661 | 35.11 |