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

Googmeister wrote:
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.

I didn't know that the lower-bound was dependent on the model of
computation. The book where I got this problem from does mention
decision trees and uses it proves that the lower-bound of
comparison-based sorting is Big-Omega(n lg n). I will definitely be
looking into this.

Note to all: I'm dealing with comparison-based algorithms in my first
post.

.

Relevant Pages

  • Re: attempt at qsort implementation
    ... qsortis not required to implement any particular sort algorithm. ... It's just supposed to sort. ... out of order by sorting them and returning the first one. ... A recursive bogosort uses bogosort to sort the possible orders by ...
    (comp.lang.c)
  • Re: The ultimate luxury ?
    ... This is not sorting. ... My definition in terms of imposing a linear order on a set is abstract ... and corresponds not to the algorithm of sorting, ...
    (sci.physics)
  • Re: The Partition-Exchange Sort algorithm
    ... You are right, of course, that the sizes of the B's can differ ... partitioning of B removes all values within B that are outside of ... example, a reversed list is handled by sorting the first half, ... algorithm that I thought was pretty neat. ...
    (comp.programming)
  • Re: Sorting lists in .Net - why it sucks
    ... Wintellect has written a set of generic collection classes that support what you are looking for. ... Normal lists are expected to store duplicate values, ... Normal sorting algorithms are just ... I don't know what sort algorithm did Microsoft use, ...
    (microsoft.public.dotnet.general)
  • Re: Sorting lists in .Net - why it sucks
    ... Wintellect has produced the "Power Collections Library" to bring some of the C++ Standard Template Library's collection classes to the CLR programmer. ... Normal lists are expected to store duplicate values, ... Normal sorting algorithms are just ... I don't know what sort algorithm did Microsoft use, ...
    (microsoft.public.dotnet.general)