puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: pete on 12 Jun 2005 16:53 spinoza1111(a)yahoo.com wrote: > > pete wrote: > > spinoza1111(a)yahoo.com 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. > > 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". Your exactly O(n * n) algorithm, is further away from O(n) than a O(n * log(n)) algorithm would be. There's just no way that your algorithm is close to O(n). In sorting and searching algorithms, you generally can't do worse than O(n * n), without deliberately trying. -- pete
From: spinoza1111 on 12 Jun 2005 23:23 CBFalconer wrote: > Christopher Barber wrote: > > spinoza1111(a)yahoo.com wrote: > >> Christopher Barber wrote: > >>> spinoza1111(a)yahoo.com wrote: > >>>> pete wrote: > >>>>> spinoza1111(a)yahoo.com 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. > > The above sentence needs an early comma. There's only one sentence. Boo hoo. IF you understand it enough to have the above opinion, then the sentence does its job. Complementary to the false consciousness of overidentification with management is the false consciousness of pretending to speak for the person who doesn't comprehend the text when you understand, or pretend to understand, sufficient to revise the text. I remain disturbed by your failure to read the post, and this reductionism of discussion to biography. It makes, as I have stated, this ng useless for technical discussion or the formation of a programmer consciousness distinct from the needs of an uncaring management who is only amused by people who have no clear conception of their interests. > > > > > 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. > > > >> 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. > > That depends on the definition of '2'. Obviously, 2 has its ordinary meaning. If you're trying to be a smartass, don't quit your day job. > > > > 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? > > > >>> 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. > > I think it is a shame the way people pick on poor Nilges, just > because he is ignorant of various things, and has a slight tendency > to be portentously profligate with Freudian verbiage about very > little, and to redefine words to suit his view. I can simply > refute his claim by defining 2 as identical to 1/3. Having done > this, all even numbers become divisible by 3. See how easy it is? > And I did it with an O(1) algorithm! > > So let's pay him and his thoughts the respect they deserve. > Yeah, lets. For it remains the case despite your word-games, which bear no resemblance to my writing at all, that for n>0, n*n/2 is less than n*n by a number greater than the infinitesimal. Even for n=1, chump. > -- > "If you want to post a followup via groups.google.com, don't use > the broken "Reply" link at the bottom of the article. Click on > "show options" at the top of the article, then click on the > "Reply" at the bottom of the article headers." - Keith Thmpson
From: pete on 13 Jun 2005 00:00 spinoza1111(a)yahoo.com wrote: > To insist that > this has any relation to the real world It has nothing to do with the real world. It's a puzzle, Ed. The object of the puzzle, was to find an O(n) solution. An O(100 * n) solution would have been fine. An O(n * n / 1000000) solution, wouldn't. There's no small n in the puzzle, just a requirement for an O(n) solution. -- pete
From: Gerry Quinn on 13 Jun 2005 08:18 In article <1118633035.143057.281510(a)f14g2000cwb.googlegroups.com>, spinoza1111(a)yahoo.com says... > Yeah, lets. For it remains the case despite your word-games, which bear > no resemblance to my writing at all, that for n>0, n*n/2 is less than > n*n by a number greater than the infinitesimal. Even for n=1, chump. Irrelevant, since if you are considering constants the correct comparison is between: (k1)( n^2 ) and (k2)( n^ 2 / 2 ) There is no knowing how k1 compares to k2. Although it may be worth noting that k2 contains a component related to the time taken to delete an array element. - Gerry Quinn
From: spinoza1111 on 13 Jun 2005 09:38
Gerry Quinn wrote: > In article <1118633035.143057.281510(a)f14g2000cwb.googlegroups.com>, > spinoza1111(a)yahoo.com says... > > > Yeah, lets. For it remains the case despite your word-games, which bear > > no resemblance to my writing at all, that for n>0, n*n/2 is less than > > n*n by a number greater than the infinitesimal. Even for n=1, chump. > > Irrelevant, since if you are considering constants the correct > comparison is between: > > (k1)( n^2 ) and (k2)( n^ 2 / 2 ) > > There is no knowing how k1 compares to k2. Although it may be worth > noting that k2 contains a component related to the time taken to delete > an array element. In the solution where delete is not allowed the average time is n^2/2 times THE SAME K as the purely O(n^2) solution. The assumption was that delete would be equivalent to setting a link "past" the deleted item, and I rejected the idea of a brute force array delete, in which entries are moved, for obviously this makes the execution much slower. > > - Gerry Quinn |