Re: Aspiring highest-order programmer

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

Date: 11 Jun 2004 18:31:22 -0700

blmblm@myrealbox.com wrote in message news:<2it7huFqphj4U1@uni-berlin.de>...
>
> Now here's where you've probably lost most of us.
>
> *O(n*n) algorithms ARE polynomial.* So are any algorithms whose

Ok, I am wrong here and participating in creating a confusing and
useless discussion about a subject on which I am NOT qualified to
speak with any authority. I am insufficiently acquainted with recent
theory to properly use terminology and in particular n*n is a
polynomial.

This is the SECOND time I have made this error in terminology.

This discussion is confusing and useless because while your motivation
is good, other participants are nursing old wounds and as such are
adding to the confusion.

As a nonspecialist in this area, I will only say that Knuth taught me
how to derive the execution time formula and determine its "order".
Skiena showed me that there has been a lot of arcane theoretical work
done since Knuth, most of it useless in "programming".

As a nonspecialist, I misused terminology. This is no crime in my
book, for people of high intelligence read beyond terminology in a
Structuralist fashion.

They can see when I confusingly refer to n*n as a nonpolynomial what I
mean is its order >1.

However, in this venue, the misuse is a thoughtcrime and also might
confuse newbies. I don't case about committing thoughtcrimes but I do
not wish to confuse newbies.

Therefore I won't respond to any further posts on this particular
matter.

> execution time can be expressed as a polynomial in "problem size"
> (a term I'll leave vague because I'm guessing at least we all have
> the same idea of what it means in this context). An O(n**100)
> (n to the 100th power) algorithm is polynomial. It's not fast,
> and execution time grows pretty rapidly, but .... Oh, it looks
> like you're continuing your thoughts in another post. I'll continue
> in a reply to that one.
>
> >For example, if for some reason I need a rather odd-shaped sort, where
> >an existing tool cannot be used (perhaps because it does not support
> >the sort ordering relationship) I will code a quick "exchange" sort
> >which is order n*n.

Nonpolynomial order is where the execution time formula is x**y not
O(x*x).

I do think that post-Knuth, the theorizing evolved away from anything
that might actualy be useful to working programmers.

Thus it appears to me that "an algorithm whose complexity is
nonpolynomial" has received undue focus in the literature when in fact
the engineering problem is reducing the ORDER of a polynomial to the
minimum possible level.

> >>
> >> [ snip ]

Relevant Pages

  • Re: Im newbie so I might understand more
    ... or stochastic control maybe better. ... very confusing. ... Tuning a system by observing its behavior and with a range of tuning adjustments is a way to deduce its transfer function. ... It make no sense for me to claim that a car is useless because it might be unstable. ...
    (sci.engr.control)
  • Re: How to check if the n-th part of an array of Strings exist?
    ... It is neither useless nor confusing. ... all nums are in monotonically increasing order ... | Return T if its arguments are in strictly increasing order, ...
    (comp.lang.java.programmer)
  • Re: TCP connect in Non Blocking Mode
    ... useless even though it's harmless. ... In that case, it is _not_ useless, unless ... Arguing about who is doing "cargo cult programming" may ... but it is just confusing for those of ...
    (comp.unix.programmer)
  • Re: How to check if the n-th part of an array of Strings exist?
    ... Shame that means something useless instead. ... Convert the boolean to a number to do the other comparison. ... It is neither useless nor confusing. ... checking that a value is in a range is very common. ...
    (comp.lang.java.programmer)
  • Re: Analyzing this Progression
    ... You saw my responses to your initial post over at ... I hope that wasn't too confusing. ... Terminology can be a big issue when you're ... Joey Goldstein ...
    (rec.music.theory)