A general Sequential Time-Space Tradeoff for Finding Unique Elements

An optimal $\Omega (n^2 )$ lower bound is shown for the time-space product of any R branching program that determines those values which occur exactly once in a list of n integers in the range $[1,R]$ where $R \geqq n$. This $\Omega (n^2 )$ 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).