A time-space tradeoff for sorting on nonoblivious machines

A model of computat ion is introduced which permits the analysis of both the time and space requirements of non-obl ivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on compar isons of individual inputs requires t ime-space product proport ional to n*. 1. MOTIVATION AND CONTRAPOSITION TO PREVIOUS RESEARCH The traditional approach to studying the complexity of a problem has been to examine the amount of some single resource (usually time or space) required to perform the computation. In an effort to better understand the complexity of certain problems, recent attention has been focused on examining the tradeoff between th