Re: Aspiring highest-order programmer

From: Edward G. Nilges (spinoza1111_at_yahoo.com)
Date: 06/16/04 

Date: 15 Jun 2004 17:08:46 -0700

blmblm@myrealbox.com wrote in message news:<2j8qvaFsrkveU1@uni-berlin.de>...
> In article <f5dda427.0406132148.3e98ab42@posting.google.com>,
> Edward G. Nilges <spinoza1111@yahoo.com> wrote:
>
> [ big snip ]
>
> >And as I have said, no practical programmer can afford to be much
> >interested in programs whose execution time formula increases more
> >rapidly than the polynomial x*x, for the simple reason that O(x*x)
> >algorithms already suck.
>
> Okay, a question for anyone else still following this discussion:
>
> Granted that all other things being equal O(n log n) is better than
> O(n*n), and O(n) is better still ....
>
> Suppose you have a problem for which the best (fastest) known
> algorithm is O(n*n). Would you consider this problem "insoluble for
> problem sizes big enough to be interesting"? In my understanding,
> this *is* true for problems for which the best known algorithms are
> exponential-time, but not for problems where there are polynomial-time
> algorithms (well, of reasonable but >=2 degree). But maybe I just hang
> out too much with scientific-computing types, where the acceptable
> time for coming up with an answer can be defined more by "how long
> can I work on this before I need to publish another paper?" than by
> "how long will an interactive user be willing to wait for a response?"

I'd at least consider trying to discover a better algorithm, even at
the cost of changing the rules as in the case of simulated annealing.

>
> [ snip ]
>
> >It sounds to me that participants in this discussion know about NP
> >completeness but don't have a feel for calculus in the sense of being
> >able to tell, from a practical program's graph of execution time, the
> >derivative of its execution time formula by feel. Since I sucked at
> >calculus but can do this, I tremble for the future.
>
> I'm not sure that's true. I think it's fairly typical in an academic
> CS program for students to be taught a formal mathematical definition
> of this O(n) stuff, and as part of that they are usually told that
> all O(n) functions have "the same shape" (straight line), all O(n*n)
> have "the same shape" (parabola), etc. This seems to me to be much
> the same thing you're talking about.
>
Kewl
> [ snip ]
>
> >> But the thing is, O(n*n) algorithms are not horrible -- yes, they're
> >> "slower" in some meaningful sense than O(n) algorithms, but an O(n*n)
> >> algorithm is still reasonable for pretty large inputs.
> >>
> >Not in the real world. Graph the execution time formula willya.
>
> Have done so on many occasions. Certainly worse than O(n), but much,
> much better than O(n!).
>
The MIS programmer doesn't control n, perhaps, as much as the
scientific programmer, because his boss and the CEO want to conquer
the world and thus expand n beyond all reason. Of course, there is no
reason for the MIS programmer to go along with this.

> >O(n*n) behavior causes the well-known crisis that occurs when the test
> >team thinks the code works and hands it off to the user. The user
> >subjects the code to large n, and the system slows to a crawl.
>
> Hm. I think we might be thinking of different criteria for acceptable
> speed. See note above about hanging out with scientific-computing
> types.
>
> [ snip ]
>
> >> The theory of NP completeness is related to all of this, but to
> >> some extent a different ball of wax. As another poster said, NP
> >> completeness is a property of problems, not algorithms. I mean,
> >> I can come up with an O(n!) algorithm for sorting, but that doesn't
> >> make sorting an O(n!) problem. The best known sorting algorithm is
> >
> >No, it makes you the proud creator of a solution that sucks. I've been
> >there, so this is not a flame.
> >
> >> -- hm, I think there are some subtle details I'm not remembering
> >> here, but I think in general it can be proved that you can't do
> >> much better than O(n log n)? Now, *that*'s kind of interesting,
> >
> >n log n is sweet. Again, graph it. The rate of acceleration slows
> >down.
>
> I don't need to graph this one again either (though agreed that this
> is worth doing if you haven't tried it). I'm familiar with the fact
> that O(n log n) functions grow faster than O(n) functions but more
> slowly than O(n*n).
>
> My point was that it's interesting to speculate (or know) whether
> O(n log n) is the best that can be done. A similar line of thinking
> applies to the question of "is P = NP?" The actual speculating might
> be left to those pointy-headed academics, but it seems to me that if
> they come up with a formal proof that a general-purpose sorting
> algorithm must always have execution time at least O(n log n), that's
> a useful result for practical programmers to know about.
>
Perhaps in quantum computing we shall discover O(1) algorithms where
the graph is a straight line, and in which speed doesn't increase at
all when n is increased, or O(inverse log) where the speed decreases
when you increase n and approaches 0.

In a biological computing model, let us say, where microorganisms do
your computing in their own self-interest by eating units of n and
excreting outputs, adding n could arguably make them stronger and
happier.

Electronic computing machines are at best unaffected by increasing
their loads. Apart from the relatively minor phenomenon that
well-written software gets better when exposed to a variety of inputs,
at best a computing device shows little wear and tear, and when
equipped with a typical operating system, like Windows, that over time
experiences entropy (in the form of acquisition of cookies, useless
entries in the Registry, expired demo copies of software, soft-core
porn and games), loads degrade performance.

Whereas a biological system often conforms to Nietzche's aphorism:
what does not kill me makes me stronger.

Perhaps the very idea that a computing machine must slow down when you
add inputs is out of date.

In quantum computing, something about which I know very little, it
would be highly nifty to discover algorithms of such velocity that the
answer came before the question.

> [ snip ]

Relevant Pages

  • Re: Aspiring highest-order programmer
    ... >> Edward, maybe I didn't read the right parts of the right discussion ... >> more valuable to a working programmer than any formal definition. ... >The use, then, I make of the theory is to rank algorithms according to ... >particular...to prefer algorithms whose execution time formulae are ...
    (comp.programming)
  • Re: Hobby vs University vs Corporate Robotics
    ... The algorithms are of varying quality. ... of any relevance to the robotic vision problem. ... Windoze programmer isn't something I want to do ...
    (comp.robotics.misc)
  • Re: off-topic: Why is lisp so weird?
    ... > algorithms more easily with one language than you do with another. ... a language that forces you to pay attention to low-level ... Some languages forces the programmer to pay ...
    (comp.programming)
  • Re: off-topic: Why is lisp so weird?
    ... > algorithms more easily with one language than you do with another. ... a language that forces you to pay attention to low-level ... Some languages forces the programmer to pay ...
    (comp.lang.lisp)
  • Re: off-topic: Why is lisp so weird?
    ... > algorithms more easily with one language than you do with another. ... a language that forces you to pay attention to low-level ... Some languages forces the programmer to pay ...
    (comp.lang.cpp)