A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.
No takes yet. Share an insight, caveat, or question.
Borodin et al. (1979) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: