A simple proof of a time-space trade-off for sorting with linear comparisons

AbstractIt is shown how to extend the techniques originally used to prove a lower bound of Ω(n2) for the product of the time and space consumed for sorting in branching programs with elementary comparisons, to the case of linear branching programs where linear functions on n input elements can be computed in unit time