A TIME-SPACE TRADEOFF FOR ELEMENT DISTINCTNESS

A. Borodin et al. have previously proved that to sort n elements requires TS equals OMEGA (n**2), where T equals time and S equals space on a comparison-based branching program. Although element distinctness and sorting are equivalent problems on a computation tree, the stated tradeoff result does not immediately follow for element distinctness or indeed for any decision problem. In this paper, we are able to show that TS equals OMEGA (n**3**/**2 (log n)** one-half ) for deciding element distinctness (or the sign of a permutation).