Re: efficient comparison

Richard Heathfield <rjh@xxxxxxxxxxxxxxx> writes:

(Query: the algorithm is actually O(a log a + b log b + a + b) - am I
right in thinking that this reduces to O(n log n) where n = a + b?)

Yes, I think so, though the traditional definition of Big-O falls
apart when extended to functions of more than one variable. This has
been pointed out only quite recently and I think the work is as yet
unpublished:

http://people.cis.ksu.edu/~rhowell/asymptotic.pdf

None of the problems occur with f(x) = x log x.

--
Ben.
.