Subj : Re: puzzle
To   : comp.programming
From : cri
Date : Tue Jun 28 2005 05:19 pm

On Tue, 28 Jun 2005 15:46:27 +0100, Ben Bacarisse
<ben.usenet@bsb.me.uk> wrote:

>On Tue, 28 Jun 2005 01:01:08 -0700, spinoza1111 wrote:
>
>> Given enough of anything, anything will work. The point being that the
>> problem is O(n^2) and not O(n) because you have to introduce a
>> conversion magical from the standpoint of theory to make it O(n)
>
>It is not usual to ascribe complexities to problems.  It can be done, but
>it is very hard (problems are usualy assigned to broader categories like
>P, NP, NP-Hard and so on).  For the *problem* to be O(n^2) you would have
>to show that *any* algorithm that solves it required *at least* O(n^2)
>time (or whaterv the measure was).
>
>Two algoroithms have been outlined that are O(n) if the size of the
>numbers is bounded: not one, two.  One uses XOR, the other partitions the
>array about (ideally) its median element.  How on earth can the problem be
>O(n^2) then?

Oddly enough, he is correct, albeit I doubt for the reasons he
imagines.  The standard definition of O() is that the function inside
the O() is bigger than the function on the left side.  IOW

	f(x) = O(g(x)) => There exists X and positive C such that for
all x>X
	|f(x)| <= C*|g(x)|

What this implies is that something that is O(n) also is O(n*n) etc.
Many programmers and computer scientists (including myself) have
fallen into the habit of treating O() as meaning "the same size",
i.e., there are positive constants C1 and C2 such that

	  C1*|g(x)| <= |f(x)| <= C2*|g(x)|

We really do want O() to mean "bigger than" because in analysis we
often have a bound without knowing whether it is the best bound
possible.  In 1976 Knuth suggested Theta as a notation for being of
the same order.  I suppose it has become standard but it certainly is
cumbersome in ordinary text.
 
>
>If you exclude XOR, for bouned numbers, the same solution can be written
>using a *constant* number of divisions and odd/even tests (mod 2
>operations) in place of each XOR.  The result is an O(n) algorithm that
>does not use XOR.  If you insist on sticking with your O(n^2) claim you
>must at least falsify the arguments that these two algorithms are O(n).

As a note sorting the array is a much more general solution (when
applicable) because it permits us to identify all discrepancies.

[snip sage comments on the value of puzzles]
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

.