Re: On the complexity of determining whether n numbers are distinct


eKo1 wrote:
There are two algorithms I can think of that determines whether n
numbers are distinct:

1. Compare each number with every other number. If you find two that
are the same, the numbers are not distinct.
2. Sort the numbers. Loop through the sorted list and if you find that
the ith and (i + 1)th entries in the list are the same, the numbers are
not distinct.

The number of comparisons in the first algorithm is proportional to n^2
and in the second to n lg n in the worst-case (viz. that all numbers
are distinct).

I want to prove that any algorithm A, in the worst-case, has to do at
least a number of comparison s proportional to n lg n. I've read that
this can be shown by reducing the problem to one of sorting but the
proof is bogus because it takes A, changes it to A' (which does
sorting) and then incorrectly states that both A and A' contain the
same number of comparisons.

Before proving it, you have to be precise about your model of
computation, e.g., what operations are permitted. The paper "Lower
bounds for algebraic computation trees" by Michael Ben-Or proves the n
log n lower bound in the algebraic decision tree model of computation.

.

Relevant Pages

  • Re: [OT] stable algorithm with complexity O(n)
    ... I have to create stable algorithm for sorting n numbers from interval ... lower bound for sorting is O. ... To beat n * log_2 n just use a bucket sort: ... maximum you can sort them digit by digit for O, ...
    (comp.lang.python)
  • Re: Sorting by complex alphanumeric data
    ... Access uses 30 as the lower bound for rwo digit ... I didn't know that you could write statements into the sorting and grouping ... most likely could use in the Report Sorting & Grouping what I gave you above ...
    (microsoft.public.access.reports)
  • Re: [OT] stable algorithm with complexity O(n)
    ... Unless I grossly miss out on something in computer science 101, the lower bound for sorting is O. ... The lower bound for sorting where you make a two way branch at each step is O, but if you can choose between k possible orderings in a single comparison you can get O. ... To beat n * log_2 n just use a bucket sort: for numbers with a known maximum you can sort them digit by digit for O, and if you don't restrict yourself to decimal then k can be as large as you want, so for the problem in question I think you can set k=n and ==1 so you get O ...
    (comp.lang.python)
  • Re: stable algorithm with complexity O(n)
    ... lower bound for sorting is O. ... To beat n * log_2 n just use a bucket sort: ... The generic sort theorems also assume you can compare arbitrarily ...
    (comp.lang.python)