<p>Any certificate (proof) of distinctness that uses only &lt;, = and > must include comparisons between each pair of adjacent elements in the sorted order. Therefore any certificate of distinctness gives enough information to sort and hence the standard information-theoretic lower bound for sorting applies to any deterministic distinctness algorithm as well.</p>

CC BY-SA 2.5
2010-10-15T16:52:46.593Z
This argument works for comparison trees, but not (directly) for more general decision tree models.
Jeffε
CC BY-SA 2.5
2010-10-15T17:01:55.977Z
JeffE: I agree. I doubt that there's a simple enough proof for Magnus's purposes that works in a more general model.
Warren Schudy
CC BY-SA 2.5
2010-10-17T12:21:07.430Z
Right. Comparison trees is fine for my application – so I guess this is pretty close to what I'm looking for. My application was explaining the idea of hardness proofs, including reducing to sorting, so the fact that the sorting proof is used here sort of short-circuits the whole thing. I guess I should have stated that explicitly :-)
Magnus Lie Hetland
CC BY-SA 2.5
2010-10-15T16:08:03.700Z
2010-10-15T16:08:03.700Z
Warren Schudy
<p>I am not sure if I understand the question correctly, but the proof by Dobkin and Lipton [DL79] that the uniqueness problem on <i>n</i> numbers requires Ω(<i>n</i> log <i>n</i>) comparisons in the linear decision tree model is much easier than the stronger result in the algebraic computation tree model by Ben-Or [Ben83] (not surprisingly).</p>

<p>References</p>

<p>[Ben83]  Michael Ben-Or.  Lower bounds for algebraic computation trees.  In <em>Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983)</em>, pp. 80–86, April 1983.  <a href="http://doi.acm.org/10.1145/800061.808735">http://doi.acm.org/10.1145/800061.808735</a></p>

<p>[DL79] David P. Dobkin and Richard J. Lipton.  On the complexity of computations under varying sets of primitives.  <em>Journal of Computer and System Sciences</em>, 18(1):86–91, Feb. 1979.  <a href="http://dx.doi.org/10.1016/0022-0000(79)90054-0">http://dx.doi.org/10.1016/0022-0000(79)90054-0</a></p>

CC BY-SA 2.5
2010-10-15T16:56:03.243Z
In short: Consider the space R^n of all possible inputs.  The set of positive inputs has n! connected components, one for each permutation.  On the other hand, the subset inputs that can reach any leaf in a linear decision tree is convex, and therefore connected.  Thus, any linear decision tree that determines uniqueness has at least n! leaves.
Jeffε
CC BY-SA 2.5
2010-10-15T16:59:52.723Z
A more subtle argument is required for the special case of integer inputs.  See Lubiw and Rács, "A lower bound for the integer element distinctness problem", *Information and Computation* 1991; or Yao, "Lower bounds for algebraic computation trees with integer inputs", FOCS 1989.
Jeffε
CC BY-SA 2.5
2010-10-15T18:54:58.253Z
@JeffE: Your short explanation is wonderful.  Also thank you for the pointer to interesting results.  It never occurred to me that the lower bound by Ben-Or does not immediately apply to the case where the input is restricted to integers!
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-15T19:18:32.837Z
Jeff: these should be in an answer !
Suresh Venkat
CC BY-SA 2.5
2010-10-17T12:09:32.990Z
Thanks to both Tsuyoshi Ito and JeffE. I've seen the R^n space proof before (in a setting using adversarial arguments). I thought it was a bit too complex for my target audience when I first read it, but I guess maybe it isn't, really. Thanks. (I've also seen the paper on the integer case – I think I won't go into that in my lecture… :)
Magnus Lie Hetland
CC BY-SA 2.5
2010-10-15T16:02:27.457Z
2010-10-15T16:02:27.457Z
Tsuyoshi Ito
<p>There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's simple enough to use in a first course in algorithm analysis and design. The same “level of difficulty” as the lower bound for sorting would be fine. Also, any approach (e.g., combinatorial or based on information theory) would be OK. Any suggestions?</p>

CC BY-SA 2.5
2010-10-15T16:02:49.337Z
What model of computation do you have in mind? If the items are small integers one can do $o(n \log n)$ by sorting. If the items can only be compared for inequality there seems to be a $\Omega(n^2)$ lower bound. Is it correct to infer from the answer you're looking for that the items are linearly ordered and can be compared for <, =, > but no other operations?
Warren Schudy
CC BY-SA 2.5
2010-10-15T19:16:37.287Z
Warren’s question in his comment is a good call.  Related to this, the comment by David Eppstein on [another question](http://cstheory.stackexchange.com/questions/1658/testing-whether-a-set-of-n-points-in-the-plane-form-a-convex-n-polygon-in-onlogn) is insightful, where he emphasizes the importance of specifying the computational model when we talk about this kind of lower bounds.  By the way, I am not sure if it makes sense to list “algebraic computation trees” (a model of computation) and “adversarial arguments” (a proof method) side by side.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-17T12:04:44.123Z
Very good points. My application here is explaining about hardness proofs by reduction – for example by reducing from uniqueness to sorting (and several other problems). Therefore, I'm assuming the same basic operations as when working with comparison sorting (so that the reduction will work). (Or, I guess, anything equivalent to the RAM with real numbers.)
Magnus Lie Hetland
<cc.complexity-theory><lower-bounds><proofs>
Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness?
Magnus Lie Hetland
# Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness?

(Asked by: username_0 on 2010-10-15)

There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's simple enough to use in a first course in algorithm analysis and design. The same “level of difficulty” as the lower bound for sorting would be fine. Also, any approach (e.g., combinatorial or based on information theory) would be OK. Any suggestions?

**Tags:** cc.complexity-theory, lower-bounds, proofs

> **Comments:**
> **username_1**: What model of computation do you have in mind? If the items are small integers one can do $o(n \log n)$ by sorting. If the items can only be compared for inequality there seems to be a $\Omega(n^2)$ lower bound. Is it correct to infer from the answer you're looking for that the items are linearly ordered and can be compared for <, =, > but no other operations?  
> **username_2**: Warren’s question in his comment is a good call.  Related to this, the comment by David Eppstein on [another question](http://cstheory.stackexchange.com/questions/1658/testing-whether-a-set-of-n-points-in-the-plane-form-a-convex-n-polygon-in-onlogn) is insightful, where he emphasizes the importance of specifying the computational model when we talk about this kind of lower bounds.  By the way, I am not sure if it makes sense to list “algebraic computation trees” (a model of computation) and “adversarial arguments” (a proof method) side by side.  
> **username_0**: Very good points. My application here is explaining about hardness proofs by reduction – for example by reducing from uniqueness to sorting (and several other problems). Therefore, I'm assuming the same basic operations as when working with comparison sorting (so that the reduction will work). (Or, I guess, anything equivalent to the RAM with real numbers.)  

---

## 2 answers

### Answer by username_1 on 2010-10-15. Score: 5 | Accepted answer

Any certificate (proof) of distinctness that uses only <, = and > must include comparisons between each pair of adjacent elements in the sorted order. Therefore any certificate of distinctness gives enough information to sort and hence the standard information-theoretic lower bound for sorting applies to any deterministic distinctness algorithm as well.

> **Comments:**
> **username_3**: This argument works for comparison trees, but not (directly) for more general decision tree models.  
> **username_1**: JeffE: I agree. I doubt that there's a simple enough proof for Magnus's purposes that works in a more general model.  
> **username_0**: Right. Comparison trees is fine for my application – so I guess this is pretty close to what I'm looking for. My application was explaining the idea of hardness proofs, including reducing to sorting, so the fact that the sorting proof is used here sort of short-circuits the whole thing. I guess I should have stated that explicitly :-)  

---

### Answer by username_2 on 2010-10-15. Score: 8

I am not sure if I understand the question correctly, but the proof by Dobkin and Lipton [DL79] that the uniqueness problem on *n* numbers requires Ω(*n* log *n*) comparisons in the linear decision tree model is much easier than the stronger result in the algebraic computation tree model by Ben-Or [Ben83] (not surprisingly).

References

[Ben83] Michael Ben-Or. Lower bounds for algebraic computation trees. In *Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983)*, pp. 80–86, April 1983. <http://doi.acm.org/10.1145/800061.808735>

[DL79] David P. Dobkin and Richard J. Lipton. On the complexity of computations under varying sets of primitives. *Journal of Computer and System Sciences*, 18(1):86–91, Feb. 1979. <http://dx.doi.org/10.1016/0022-0000(79)90054-0>

> **Comments:**
> **username_3**: In short: Consider the space R^n of all possible inputs.  The set of positive inputs has n! connected components, one for each permutation.  On the other hand, the subset inputs that can reach any leaf in a linear decision tree is convex, and therefore connected.  Thus, any linear decision tree that determines uniqueness has at least n! leaves.  
> **username_3**: A more subtle argument is required for the special case of integer inputs.  See Lubiw and Rács, "A lower bound for the integer element distinctness problem", *Information and Computation* 1991; or Yao, "Lower bounds for algebraic computation trees with integer inputs", FOCS 1989.  
> **username_2**: @JeffE: Your short explanation is wonderful.  Also thank you for the pointer to interesting results.  It never occurred to me that the lower bound by Ben-Or does not immediately apply to the case where the input is restricted to integers!  
> **username_4**: Jeff: these should be in an answer !  
> **username_0**: Thanks to both username_2 and JeffE. I've seen the R^n space proof before (in a setting using adversarial arguments). I thought it was a bit too complex for my target audience when I first read it, but I guess maybe it isn't, really. Thanks. (I've also seen the paper on the integer case – I think I won't go into that in my lecture… :)  

---

