The problem may be solved by sorting the list and then checking if there are any consecutive equal elements; it may also be solved in linear expected time by a randomized algorithm that inserts each item into a hash table and compares only those elements that are placed in the same hash table cell.
The number of comparisons needed to solve the problem of size
invokes big theta notation, meaning that the problem can be solved in a number of comparisons proportional to
(a linearithmic function) and that all solutions require this many comparisons.
The same lower bound applies as well to the expected number of comparisons in the randomized algebraic decision tree model.
[3][4] If the elements in the problem are real numbers, the decision-tree lower bound extends to the real random-access machine model with an instruction set that includes addition, subtraction and multiplication of real numbers, as well as comparison and either division or remaindering ("floor").
A single-tape deterministic Turing machine can solve the problem, for n elements of m ≥ log n bits each, in time O(n2m(m+2–log n)), while on a nondeterministic machine the time complexity is O(nm(n + log m)).
[6] Quantum algorithms can solve this problem faster, in
[7] Yaoyun Shi first proved a tight lower bound when the size of the range is sufficiently large.
[8] Ambainis[9] and Kutin[10] independently (and via different proofs) extended his work to obtain the lower bound for all functions.
This time is optimal under the decision tree model of computation.