Author: Stan Eisenstat
Subject: Re: [Cs223] Inequality Testing
Date: Tuesday, 03 Mar 2020, 07:51:25

    > Message Posted By: Unknown
    >
    > What is the goal of the inequality testing example in the adversary
    > arguments lecture? Is it to sort all of the values in an array? If so,
    > then I understand why the time would be nlogn. Or all of the items in S
    > just permutations of 1,...,n such that either two values are equal, that
    > values are all less than each other, or that all value values are greater
    > than each other?

The purpose of the weights version of element uniqueness
is to illustrate that changing the model of computation
(to allow questions of the form "Is X[I]  x[J]?
instead of "Is X[I] = X[J]?") can lead to new algorithms
(e.g., sorting plus checking adjacent weights) that have
lower complexity than the lower bound that was previously
established.

--Stan-