3
$\begingroup$

Given a collection of $n$ numbers, $S$, the question is to decide whether all the elements of $S$ are distinct from each other. If they are distinct from each other (no two of them are the same), print "Yes". Otherwise print "No".

I know the worst case time complexity of this question is $\Theta \left ( n\log n \right )$. Of course it is based on comparison among elements. But I can't figure out how to prove this. Perhaps using the decision tree?

$\endgroup$
4
$\begingroup$

The lower bound $\Omega(n\log n)$ is a classical result of Ben-Or, Lower bounds for algebraic computation trees. The problem itself is known as element distinctness, and other lower bounds are proved by reduction to this fundamental lower bound. Ben-Or's lower bound is proved in the algebraic decision tree model, a generalization of the comparison model in which each decision can be made on the basis of evaluating the sign of an arbitrary polynomial in the inputs (rather than just the polynomials $a_i - a_j$). In order to get a meaningful lower bound, we only allow polynomials of constant degree (the lower bound works for any fixed constant): otherwise we can detect whether all elements are unique by evaluating the polynomial $$ \prod_{i<j} (a_i - a_j). $$ (The actual model considered by Ben-Or, algebraic computation trees, is even more general: he considers "programs" with statements of the form $x = y \pm z$, $x = yz$, $x = y/z$, $x = \sqrt{y}$ and $x = \alpha y$ for real $\alpha$, as well as conditional statements which depend on conditions of the form $x = 0$, $x > 0$ or $x \geq 0$. Each operation and conditional statement takes unit time, and the lower bound is on the worst-case running time.)

Here is a sketch of the proof in the case where decisions are made based on the sign of linear polynomials, following Jeff Erickson's notes. For each node $v$ in the algebraic decision tree, let $R(v)$ be the set of $(a_1,\ldots,a_n)$ reaching that node. It is not hard to check that $R(v)$ is connected. For each permutation $\pi \in S_n$, the set $R_\pi$ of tuples $(a_1,\ldots,a_n)$ ordered according to $\pi$ is connected, but any two $R_\alpha,R_\beta$ for $\alpha \neq \beta$ are separated by some region in which the elements are not distinct. The lower bound $\Omega(n\log n)$ immediately follows.

If the allowable conditions have higher degree, then it is no longer true that $R(v)$ is connected; but a deep theorem of Thom and Milner shows that if the decision tree is shallow then each $R(v)$ is composed of "not too many" connected components, and we get the same lower bound. (The same proof idea works for the algebraic computation trees considered by Ben-Or.)

The latest word on the subject (as of 1998) is work of Grigoriev, Karpinski, Meyer auf der Heide and Smolensky, extending the lower bound to randomized algebraic decision trees, and work of Grigoriev extending it to randomized algebraic computation trees. Their proof avoids the use of the deep result of Thom and Milnor mentioned above, and so gives an alternative "elementary" proof of Ben-Or's result.

$\endgroup$
4
$\begingroup$

I think there is something wrong with your claim that the complexity is $\Theta(n \lg n)$. At least, it is not quite that simple. You don't say where you got that claim from, but I don't think it is accurate, at least in general.

The problem can be solved faster, in some machine models. For instance, there are sorting algorithms with running time faster than $\Theta(n \lg n)$, in some machine models, and there are other ways to solve this problem -- e.g., using a hash table using a 2-universal hash function should yield a solution whose expected running time is $\Theta(n)$, under a reasonable model of computation.

What is your machine model? A RAM machine? What notion of complexity are you OK with? Worst-case running time of a deterministic algorithm? Are you OK with a randomized algorithm? The complexity of the problem will depend upon these fine details.

$\endgroup$
  • $\begingroup$ I am sorry maybe I didn't state the question clearly before. It is just an exercise from an algorithm book.$\Theta \left ( nlogn \right )$ is the worst case time complexity of this problem. And the complexity is based on the number of comparisons among elements. So I think this is a worst-case running time of all deterministic algorithms solving this problem. I am convinced by your thought and thoroughness! I haven't consider these aspects before! Thanks a lot! $\endgroup$ – tamlok Dec 10 '13 at 10:56
0
$\begingroup$

I assume that the collection is stored in an array, if it is not, then it should be able to be moved to one in linear time, unless you have an unusual storage data structure.

One way that it could be done is to first sort $S$, assuming you're sensible and use a good algorithm (whichever you prefer), this will take $\Theta(n \log n)$ time. Now as everything is in order, we know that if there are any duplicates, all the entries with the same value must be next to each other. So we can just do a linear search along the collection, checking each entry against the one after it.

$\endgroup$
  • $\begingroup$ Your answer shows that the complexity is $O(n \lg n)$, but not that the complexity is $\Omega(n \lg n)$. The latter is the non-trivial part of the problem, and I don't think the claim is even correct in general (it might be correct in some machine models but it'll be incorrect in others, I believe). $\endgroup$ – D.W. Dec 10 '13 at 6:15
  • $\begingroup$ Yes. But what you have done is to design an algorithm to solve this problem taking $\Theta \left ( nlogn \right )$ time. But this just give an upper bound of this problem. I want to prove the complexity of the problem,not of an algorithm solving it.That is the lower bound of the worse case complexity of this problem. Thanks anyway! Maybe I didn't state it clearly enough before. $\endgroup$ – tamlok Dec 10 '13 at 11:01
  • $\begingroup$ @tamlok, no just my misinterpretation. Yuval's answer seems to be the right thing though. $\endgroup$ – Luke Mathieson Dec 10 '13 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.