Re: puzzle



Christopher Barber wrote:
> spinoza1111@xxxxxxxxx wrote:
> >
> > Christopher Barber wrote:
> >
> >>spinoza1111@xxxxxxxxx wrote:
> >>
> >>>pete wrote:
> >>>
> >>>
> >>>>spinoza1111@xxxxxxxxx wrote:
> >>>>
> >>>>
> >>>>
> >>>>>You're doing O(n) searches, times a linearly shrinking array, only in
> >>>>>the worst case. N/2 the time on average it finds U. This doesn't
> >>>>>transform order n^2 because it divides by a constant and not N but it
> >>>>>is none the less a significant reduction.
> >>>>
> >>>>Whatever O(n * n / 2) could possibley mean
> >>>>is what O(n * n) actually means.
> >>>>Constant factors aren't part of big O notation.
> >>>
> >>>
> >>>Of course not. But, n*n/2 != n*n for positive n: n*n/2 < n*2 for n>0.
> >>>
> >>
> >>It is not clear to me that you understand. O(n*n) == O(n*n/2)!
> >
> >
> > D'oh. As my kids would say.
> >
> > I am very disturbed by your failure to read the post properly, and this
> > kneejerk reduction of discussion to the biographical issue of who
> > understands what, which, as I have said, makes this ng useless for
> > either discussion of technical issues or the generation of solidarity
> > or understanding among programming professionals.
>
> You should consider the possiblity that the reason that people are not
> understanding you the way you intend is because you are failing to communicate
> effectively and clearly. Your tendency to use (and sometimes misuse) obscure
> words and to insert long paragraphs of orthogonal social commentary does not
> make it easy for people to understand what you are saying.

This is a canard. The attentive reader can determine cultural
references from context and improve his general fund of culture in this
way. I should get paid for this.

This canard reasons post facto from a reader response for which I have
advanced a much more solid and much more researched explanation; it
looks at the howls of dismay and concludes prematurely I don't write no
gude. My alternative explanation is that owing to corporate
surveillance or its possibility (which the "utilitarian" philosopher
Jeremy Bentham proved equivalent), people using this ng (who in many
cases are using it in passive-aggressive style, stealing both paid
employee time and network facilities from their employers), posters
have anxiously learned to project a false face and use a false
consciousness.

This is the false and sour authority of biographical one-upmanship in
which the negative goal is establishing ONE poster as the "mark" or
scapegoat that can be a target of psychological transference for
unacceptable, if at times highly appropriate, feelings of negative
self-worth, feelings that the corporation deliberately manufactures at
middle management levels and below.

The trouble here, as I've demonstrated repeatedly, is that posters have
for a change come to the wrong shop, for instead of targeting someone
easily silenced (or like women posters in the 1980s, pushed out by
targeted campaigns, conducted by system administrators, including rape
threats) you've selected someone who's taught at three universities,
assisted John Nash with programming, published articles in the computer
press since 1976 and a recent tech book, and works internationally as
opposed to East Jesus.


>
> > For, I used the phrase "close to" as regards O(n).
> >
> > O(n*n) == O(n*n/2), of course. But it's also the case for practical
> > applications that n*n/2 < n*n.
>
> Sure, given the choice between an algorithm that costs n*n steps and one that
> costs n*n/2 steps of the same size, the latter is a better choice in terms of
> cost, but I don't known anyone other than you that would call such an
> algorithm "close to" O(n). When there are linear and O(n log n) algorithms
> that are also simpler to implement, what is the practical use case for your
> algorithm?

Read the literature on O(x), for Chrissake. See for example Skiena, The
Algorithm Design Manual
(http://www.amazon.com/exec/obidos/tg/detail/-/0387948600/qid=1118630635/sr=8-3/ref=pd_csp_3/103-4992382-6347852?v=glance&s=books&n=507846).

You don't UNDERSTAND O(x) UNTIL you know when to use O(n^2) in the
pragmatic sense where n is small and known to be small for practical
applications.

For example, for n<100, while it is almost never acceptable to use a
bubble sort, it is almost always acceptable to use an interchange sort:

for i = 1 to count-1
flag = false
for j = i + 1 to count
if a[i]>a[j] begin exchange; set flag end
end
if not flag then exit
end

Unlike the bubble sort, the interchange sort exchanges at wider
intervals and takes an early exit when no exchange occurs. It in fact
PROVES that within the very broad context of O(x) there is a great deal
of algorithm analysis to be done.

If you have small n, and if the nature of the problem is that n will
remain small over the useful life of the system, the O(n) taxonomy is
inapplicable choice of interchange over bubble and you have to look
implicitly at the exedcution time formula of both, on which O(n) is
based.

"Real world", corporate programmers need to know this. In fact, it
might be argued that they don't necessarily need ever to implement an
O(n) sort because once n passes 10e2, the genuinely real-world question
is WHY the n elements aren't in a data base, which we can trust to use
the highpower algorithms.

What's interesting is that you have in the corporate style lectured me
on the real world in a private email. But to insist in effect that O(x)
is the only possible taxonomy and that it is useless to analyze within
the category of O(n*n) is a learned form of ignorance. To insist that
this has any relation to the real world (in which as I have said, you
are all the time presented with oddly shaped situations, for example of
not being able to sort, but being able to delete) is nonsense, and it
explains the 80% failure rate of large, enterprise systems.

To be charitable, you concede that n*n/2 < n*n for positive n. But what
seems to have replaced Knuth's supple, if somewhat out of date,
discussion of algorithm complexity in The Art of Computer Programming
is "learning" which has heard, in the American corporate style, only
some sort of moral lesson: O(n) good: O(n*n) always bad.

This binarism is discussed in Derrida who shows that academics, and
academically educated people brutalized in the real world, tend to
transform neutral categories into moral judgements.

I don't "understand" O(n) in the corporate sense that I treat the
theory as a common human treasury, not a reified Secret of which one is
more in possession of, as opposed to knowing, and who, having learned
the ways of the eunuch priesthood, has necessarily learned to speak of
the Eleusinian mystery, not in straightforward and manly terms, but in
the hushed and pious terms of the mentally spayed.

A political binarism in other words increasingly infects the minds of
students and of computer programmers who selected their trade only to
make money, and avoid having to take the bus like the colored people. A
simple taxonomy becomes savagely invested with *mana* such that to be
able to write about it, as I am able, with anything like urbanity is no
longer praised but condemned as a possible heretical hermeneutic.

That is, what's bugging you is the nature of my game. Precisely to the
extent that I write in an old-fashioned style, old-fashioned in the
sense of being urbane and attempting to a form of general erudition
with due humility, I identify myself as a nonmember of the club, in
which people have learned to zip up lest their masters thrash them at
their desk.

My language is unfamiliar only because corporate life, perhaps even for
a good reason given its preconditions, has to literally destroy certain
conceptual abilities isomorphic to words like "solidarity" (where
instead programmers have to "compete" in such a manner that
"solidarity" is replaced by suck-up vertically, grab-ass horizontally,
and scapegoating downward) and "hermeneutics" (where the very idea of
questioning a sanctioned text has to be eliminated).

Also, I sense a massive resentment and desire to destroy that form of
understanding which was able to say that O(n*n/2) was "closer to" or
even "close to" O(n), which narrates the navigation in what happened to
be a search for alternative algorithms practical in the real world.

FYI, I hoped by writing urbanely to discover better and better
solutions including O(n) in the manner of Dijsktra and my FAILURE was
unnoticed. I don't have the knowledge, at this time, to prove that the
problem is O(n*n). But no-one else has done so in this thread, either,
because of all the grab-ass.

This ng if chock a block with the resentment of people who cannot write
down their understanding of mathematical concepts and whose
mathematical education is therefore not complete, no matter how many
degrees they gots from Rice, Texas A & M or Bob Jones.
>
> >>The important point is that as the size of the data set doubles, the cost of
> >>the algorithm quadruples. Dividing by two doesn't change this.
> >>
> >>>The resentment here is of ability to explain, complementary to the
> >>>inability to read shown by O'Dwyer who read a claim for O(n) when I
> >>>said "close to".
> >>
> >>When you are taking about the O() notation, there is no such thing as "close
> >>to". Something is either O(n) or it is not. O'Dwyer probably assumed that
> >>you knew that.
> >
> > It's obvious from the original post that I understand,
>
> Actually, it really was not all that obvious.

OK, I don't "understand", I don't have the *verstehen* you demand.
Let's not be peers. Let's not work together. I'd rather write and
publish 26000 lines of my OWN goddamn code and have it work than work
with people who don't in my humble opinion know their trade. I am
willing that they have jobs far away from me and I wish them success in
all their future endeavors.

But, IF I form a company, and IF I hire some guy who manifests this
form of *verstehen*, I WILL fire his ass.

A downsized, in my view inarticulate, understanding may be just what
the corporation needs today. Installing existing software and setting
parameters is radically different from what I like to do, which is
write code and then flap my gums about it with likeminded men of parts.

But installing software, setting parameters, and engaging in grab-ass
on this ng shouldn't be called "programming"!

>
> - Christopher

.

Relevant Pages

  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... I would tailor which algorithm to start with by how the student thinks ... If you only learn the beautiful side of programming, ...
    (comp.programming)
  • Re: "Sorting" assignment
    ... If you only learn the beautiful side of programming, ... elegance and beauty from the fact that we developed this algorithm ... The insertion sort can be illustrated and is ... English grammar, apparently, than many English speakers, a noun phrase ...
    (comp.programming)
  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... everyone teaches it as a first sorting algorithm. ... If you only learn the beautiful side of programming, ...
    (comp.programming)
  • Merge sort in fortran 90 for linked lists
    ... I have been programming in fortran 90 and I need the merge sort ...
    (comp.lang.fortran)
  • Re: Merge sort in fortran 90 for linked lists
    ... I have been programming in fortran 90 and I need the merge sort ...
    (comp.lang.fortran)