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

Patricia Shanahan <pats@xxxxxxx> writes:

[...]
Incidentally, the minimum number of comparisons for a sort also breaks
down if you can use the elements to index an array. Proofs of it depend
on the requirement that the only operation on the elements is pairwise
comparison.

Consider an array of integers, and increment vector element n by one for
each n in the input:

Initially, the vector is:

... 0 0 0 0 0

First number is 1, so we increment element 1:

... 0 0 0 1 0

Next number: 2; we increment element two:

... 0 0 1 1 0


Next number (i.e., 3):

... 0 1 1 1 0

Next number is 1, so increment element 1 again:

... 0 1 1 2 0

Now iterate through the vector in increasing index order. If element i
is k, write i out k times:

1 1 2 3

and the original data is sorted in O(n) operations, with no pairwise
comparisons.

Technically correct, perhaps, but all a bit silly really.
You've just replaced pairwise comparisons with increments,
comparisons to zero, and decrements, which all still need
to be counted. As your vector needs to be as large as the
largest number k, which may be very much larger than n,
the number of comparisons to zero may be much larger than
the number of pairwise comparisons you've eliminated.

.

Relevant Pages

  • vlookup - #N/A
    ... I use the false in Range_Lookup so I do not have to sort the array each time. ... Any ideas on how I can get the function to return a zero instead of the #N/A when there is no match found?? ... Is there some other function I can nest such as IF?? ...
    (microsoft.public.excel.worksheet.functions)
  • Re: array sorting question
    ... length including zero. ... I want to sort the array of arrays in such a ... way that the interior arrays with the most elements are closest to the ... middle of the main array. ...
    (comp.lang.ruby)
  • Re: On the complexity of determining whether n numbers are distinct
    ... the minimum number of comparisons for a sort also breaks ... You've just replaced pairwise comparisons with increments, ... comparison lower bound for sort is based on the limitation that the only ... I suggest adding the pairwise comparison limitation to the main question ...
    (comp.theory)
  • Re: On the complexity of determining whether n numbers are distinct
    ... You've just replaced pairwise comparisons with increments, ... comparisons to zero, and decrements, which all still need ... As your vector needs to be as large as the ...
    (comp.theory)