A GENERAL SEQUENTIAL TIME-SPACE TRADEOFF FOR FINDING UNIQUE ELEMENTS

An optimal OMEGA(n2) lower bound is shown for the time-space product of any R-way branching program that determines those values which occur exactly once in a list of n integers in the range [1, R] where R greater-than-or-equal-to n. This OMEGA(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 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 multitape Turing machines and off-line log-cost random access machines (RAMs).