Re: Re: Re: Re: programming problem about elements

*To*: mathgroup at smc.vnet.net*Subject*: [mg72535] Re: [mg72521] Re: [mg72510] Re: [mg72497] Re: programming problem about elements*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Fri, 5 Jan 2007 02:14:12 -0500 (EST)*References*: <200612301039.FAA21673@smc.vnet.net><en82hd$6or$1@smc.vnet.net> <200701030603.BAA29747@smc.vnet.net> <200701031016.FAA07246@smc.vnet.net> <200701041148.GAA18047@smc.vnet.net>

On 4 Jan 2007, at 11:48, Daniel Lichtblau wrote: > Andrzej Kozlowski wrote: > > Union is different. For default SameTest it will use Sort and then > compare elements to neighbors. This is O(n log n) due to use of Sort. > For nondefault SameTest it must compare all pairs and this is O(n^2) > complexity. This also necessitates use of the evaluator for each > equivalence check, so we have a constant factor also slowing the > process. Offhand I do not recall whether presorting is done in this > case. There is a final Sort in order to be in agreement with > documentation. > > > Daniel Lichtblau > Wolfram Research > I am not sure if my memory is not deceiving me, but I seem to remember that in some earlier versions of Mathematica, Union with user defined SameTest worked differently; I think, essentially the way it does today with the default setting of SameTest. In other words, things were first sorted and then only neighboring elements were compared, starting with the smallest. I seem to recall that this behavior caused some complaints to be posted to this list and in later versions it was changed. (I might of course be just fantasizing it all so just in case I will blame it on post-New Year hangover). But in this particular problem the old behavior (assuming that was the old behavior) would have been preferable so perhaps it might have been a good idea to have preserved it as a (non-default) option. That applies, of course, only to the real version of the problem; in the complex version I think it is really necessary to compare all pairs. Andrzej Kozlowski

**References**:**Re: programming problem about elements taken***From:*"Ray Koopman" <koopman@sfu.ca>

**Re: Re: programming problem about elements taken***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>

**Re: Re: Re: programming problem about elements***From:*Daniel Lichtblau <danl@wolfram.com>