@article {IOPORT.03963208,
    author       = {Johnson, Donald B.},
    title        = {A simple proof of a time-space trade-off for sorting with linear comparisons.},
    year         = {1986},
    journal      = {Theoretical Computer Science},
    volume       = {43},
    issn         = {0304-3975},
    pages        = {345-350},
    publisher    = {Elsevier Science Publishers, Amsterdam},
    doi          = {10.1016/0304-3975(86)90185-4},
    abstract     = {Summary: It is shown how to extend the techniques originally used to prove a lower bound of $\Omega (n\sp 2)$ 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.},
    identifier   = {03963208},
}