Go back to home Go back to 6610

An Introduction to Time-Space Tradeoff for Sorting

-by Xingzhi Luo

1.1 We may have questions about what makes a good algorithm, of course, everyone likes algorithm that takes the shortest time and smallest spaces. But actually, for most of the problems, such kind of algorithm never exits. So this problem brings another complexity problem: time-space complexity.

Definition: Time-Space complexity: the product of Time and Space T*S.

For most of problems, its time-space complexity has the following attribute: That is, for most of time, you can use less time by adding more space, or vise versa.

Bordin gave a general survey of time-space tradeoff in [3]. More recently, Paul Beame in the University of Washington did a lot of research work in trade-off for randomized computation, branching programs, undirected graph traversal…

As for Time-space tradeoff for Sorting, there are many traditional algorithms for sorting, but few of them can make tradeoff between Time and Space. Munro and Paterson gave the first time-space-focused algorithm, with [6]. Savage gave an introduction to this area in [4]. Beam proved that the lower bound for sorting is [2]. Until recently, Jakob Pagter and Thesis Rauhe gave an algorithm with upper bound equals to this lower bound , that is, their algorithm is the optimized one.

Upper bounds. Classical sorting algorithms like Quick-Sort and Merge-Sort have , in this algorithms, , and use log-sized words [5]. Of course in these algorithms the time and space and space in the algorithm are fixed and can not be trade-off.

In order to prove this theorem, Jakob gave the following lemma:

Lemma1 For , there exists a comparison based RAM algorithm which supports the operation Init(x) in time , the operation Pop in time , and whose space usage is O(m) bits.

Jakob’s algorithm to prove this theorem was steamed from the heap sorting, that is the first step is to build a sorting tree, and then recursively popup the minimum number and reconstruct the sorting tree. But the difference is, this algorithm doesn’t load the data into the sorting tree, while leaves it on the input tape.

Definitions: for an input of n numbers, , consquently divide them into m subvectors. Each node contains two number (B, P), B = 1 means the minum number is on its left branch, b = 0 on right branch. This number is used to trace the subvector which contains the minum number, as the red line shows. For node V on level t (from to to bottom is 0 to), devide V_min in to subvectors, then P means the minimum number is in the Pth subvector of V_min. V_min is the the vector that node V can reach and it contains the minimum number that node V can visit. Thus the total work space is . Filter x_f is used to recorde the minum number currently, it will be used to judge which numbers are already poped. V_L and V_R are the two sons of V.

Algorithm: Popup: trace to Root_min with B, with P find the sub vector, then Get the minimum x_min, with brute search. x_f=x_min. Rebuild: only those nodes on the path from Root_min to Root are need to refresh (totally nodes). For each node V, it only need to use brute search to find the new V_min among the sub_vector of each V_L_min and V_R_min. Total time to rebuild . Init(x): the initialization procedure is only a compare procedure from bottom to top, the time used on level t is: , so totally it’s:

So the these algorithm, we can easy to prove the lemma and Jakob’s theorm.

3. Conclusions

Jakob provided us an optimal sorting method. It’s also the lower bound for time-space complexity problem in Sorting.

[1] Optimal Time-Space Trade-O_s for Sorting, Jakob Pagter and Theis Rauhe, BRICS Report Series. http://www.brics.dk

[5] Sara Baase, Allen Van Gelder, Computer Algorithms, Introduction to Design and Analysis, Pearson Education, 2001

[6] J. I. Munro and M. S. Paterson, Selection and Sorting with Limited Storage," Theoretical Computer Science, vol. 12, pp. 315-323, 1980.