A general sequential time-space tradeoff for finding unique elements

An optimal R(n2) lower bound is shown for the time-space product of any R-way branching pro-gram that determines those values which occur exactly once in a list of n integers in the range [l, R] where R 1 n. This Q(n2) tradeoff also applies to the sorting problem and thus improves the previous time-space tradeoffs for sorting. Because the R-way branching program is a such a powerful model these time-space product tradeoffs also apply to all models of sequential computation that have a fair measure of space such as off-line multi-tape Turing machines and off-line log-cost RAMS.