ItThe isnumber knownof that,comparisons forneeded liststo solve the problem of numberssize <math>n</math>, thein problem'sa comparison-based model of computation such as a [[timedecision complexitytree]] isor [[Bigalgebraic Odecision notation|Θtree]], is <math>\Theta(''n'' \log ''n'')</math>. Here, i.e.<math>\Theta</math> invokes [[Big O notation|big theta notation]], bothmeaning that the upperproblem andcan lowerbe boundssolved onin itsa timenumber complexityof arecomparisons ofproportional orderto of<math>n\log then</math> (a [[linearithmic function]]) inand thethat [[algebraicall decisionsolutions tree]]require [[modelthis ofmany computation]],comparisons.<ref>{{citation|first=Michael|last=Ben-Or|contribution=Lower bounds for algebraic computation trees|title=[[Symposium on Theory of Computing|Proc. 15th ACM Symposium on Theory of Computing]]|year=1983|pages=80–86|doi=10.1145/800061.808735}}.</ref> aIn modelthese models of computation in which, the elementsinput numbers may not be used to index the computer's memory (as in the hash table solution) but may only be accessed by computing and comparing simple algebraic functions of their values. InFor otherthese wordsmodels, an algorithm based on [[asymptoticallycomparison optimalsort]] algorithmsolves the ofproblem linearithmicwithin timea complexityconstant isfactor knownof forthe thisbest modelpossible number of comparisons. The algebraicsame computationlower treebound modelapplies basicallyas meanswell thatto the allowable[[expected algorithmsvalue|expected arenumber]] onlyof comparisons in the ones[[randomized thatcomplexity|randomized]] can[[algebraic performdecision polynomialtree]] operationsmodel.<ref>{{citation|doi=10.1007/BF01270387|title=A oflower boundedbound degreefor onrandomized thealgebraic inputdecision datatrees|year=1996|last=Grigoriev|first=Dima|authorlink=Dima andGrigoriev|journal=Computational comparisonsComplexity|volume=6|pages=357|last2=Karpinski|first2=Marek|author2-link=Marek ofKarpinski|last3=Heide|first3=Friedhelm theMeyer|last4=Smolensky|first4=Roman|issue=4}}.</ref><ref>{{citation|doi=10.1007/s000370050002|title=Complexity resultslower ofbounds thesefor computationsrandomized computation trees over zero characteristic fields|year=1999|last=Grigoriev|first=Dima|authorlink=Dima Grigoriev|journal=Computational Complexity|volume=8|pages=316–329|issue=4}}.</ref>
The same lower bound was later proved for the [[randomized complexity|randomized]] [[algebraic decision tree]] model.<ref>{{citation|doi=10.1007/BF01270387|title=A lower bound for randomized algebraic decision trees|year=1996|last=Grigoriev|first=Dima|authorlink=Dima Grigoriev|journal=Computational Complexity|volume=6|pages=357|last2=Karpinski|first2=Marek|author2-link=Marek Karpinski|last3=Heide|first3=Friedhelm Meyer|last4=Smolensky|first4=Roman|issue=4}}.</ref><ref>{{citation|doi=10.1007/s000370050002|title=Complexity lower bounds for randomized computation trees over zero characteristic fields|year=1999|last=Grigoriev|first=Dima|authorlink=Dima Grigoriev|journal=Computational Complexity|volume=8|pages=316–329|issue=4}}.</ref>
==Quantum complexity==
It is also known that [[quantumQuantum algorithm]]s can solve this problem faster, in <math>\Theta\left(n^{2/3}\right)</math> queries. The optimal algorithm is by [[Andris Ambainis]].<ref>{{citation | last1=Ambainis | first1=Andris | author1-link=Andris Ambainis | title=Quantum walk algorithm for element distinctness | doi = 10.1137/S0097539705447311 | journal = [[SIAM Journal on Computing]] | volume = 37 | issue = 1 | year = 2007 | pages=210–239 | arxiv=quant-ph/0311001 }}</ref> [[Yaoyun Shi]] first proved a tight lower bound when the size of the range is sufficiently large.<ref>
