[OT] stable algorithm with complexity O(n)

[Steven D'Aprano]

On Sun, 14 Dec 2008 21:18:03 -0500, Roy Smith wrote:

> Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> wrote:
> 
>> All the positive thinking in the world won't help you:
>> 
>> * make a four-sided triangle;
>> 
>> * split a magnet into two individual poles;
> 
> These two are fundamentally different problems.
> 
> The first is impossible by definition.  The definition of triangle is,
> "a three-sided polygon".  Asking for a "four-sided triangle" is akin to
> asking for "a value of three which is equal to four".

That's right. But see below.


> The second is only "impossible" because it contradicts our understanding
> (based on observation) of how the physical universe works.  Our
> understanding could simply be wrong.

And arithmetic could be inconsistent, in which case it might be possible 
to prove that 3 equals 4. We don't know for sure that arithmetic is 
consistent, and according to Godel, there is no way of proving that it is 
consistent. There's no evidence that it isn't, but then, unless the 
inconsistency was obvious, how would we know?

http://www.mathpages.com/home/kmath347/kmath347.htm


> We've certainly been wrong before,
> and we will undoubtedly be proven wrong again in the future.  When it
> comes to things like electromagnetic theory, it doesn't take too many
> steps to get us to the fuzzy edge of quantum physics where we know there
> are huge questions yet to be answered.

No. I worded my question very carefully. The discovery of magnetic 
monopoles, as predicted by the fuzzy end of quantum physics, would not 
invalidate my claim. Magnets don't generate magnetic fields by the use of 
monopoles, and the discovery of such wouldn't make it possible to cut an 
ordinary magnet in two to get an individual north and south pole. That 
would like taking a rope with two ends (an ordinary rope, in other 
words), cut it in half, and finding that each piece has only a single end.

Now, you could counter with a clever solution involving splicing the rope 
to itself in such a way that it had one end and a loop at the other, er, 
end. And such a solution might be very valuable, if we needed a way to 
get a rope with a loop at one end. But it isn't solving the problem of 
cutting a rope in two and getting only two ends instead of four. It's 
solving a different problem.




-- 
Steven