Re: Aspiring highest-order programmer

blmblm_at_myrealbox.com
Date: 06/15/04 

Date: 15 Jun 2004 17:46:19 GMT

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?"

[ 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.

[ 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!).

>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.

[ snip ] 

-- 
| B. L. Massingill
| ObDisclaimer:  I don't speak for my employers; they return the favor.

Relevant Pages

  • Re: Aspiring highest-order programmer
    ... An NP algorithm, as Ian reminded us, is ... one whose execution time formula is not a polynomial. ... >>his own goddamn programming and is man enough to admit error) it was ... > reason to suspect that no such algorithm exists. ...
    (comp.programming)
  • compare 2 samples
    ... I've set a test machine up so that it switches between algorithm implementations and keeps simple timing records for each alg. ... I would like to compare the 2 results and state with some confidence that there really is a difference. ... When I first looked at the 2 results, I assumed that it was a simple one sided hypothesis test. ... Assuming that the probability distribution for execution times on a highly concurrent server is normal, we would formulate a null hypothesis that the execution time for P is greater than or equal to the execution time of Q. The alternative hypothesis being that the execution time of P is less than the execution time for Q. ...
    (sci.stat.math)
  • Re: Fastcode UpperCase B&V 2.6
    ... that execution time of a significant part of algorithm ... interruptions which wash away results of measurements even more. ... don't forget to count a delay after use MMX, ...
    (borland.public.delphi.language.basm)
  • Re: a basic question about execution speed
    ... It depends on the time complexity of the algorithm. ... the same hardware resources), must the execution time of each run be ...
    (comp.programming)
  • Re: Huge performance gap
    ... in the algorithm though it will still be considerably slower. ... and the other is an interpreted dynamic language. ... either ridiculous, or more likely in this case, simply ignorant. ...
    (comp.lang.ruby)