puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: pete on 11 Jun 2005 20:14 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. -- pete
From: Christopher Barber on 11 Jun 2005 23:19 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)! 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. - Christopher
From: spinoza1111 on 12 Jun 2005 07:49 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. 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. > > 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, and again, this transformation of discussion into a childish attempt to score biographical points is bullshit. As are lectures on the "real world" via email, for it is precisely in the real world that one discovers for any number of reasons that one can't sort pragmatically but one can delete, or vice versa, and in the real world you have to be able to analyze, and discuss, algorithms without succumbing in the individual case to crippling math anxiety or in the group case to childish attacks of the form "you don't understand". As in the case of Adorno's study of astrology readers "The Stars Down To Earth", you come here and because of corporate surveillance, you adopt Adorno's astrology reader's false consciousness: that of the corporate manager to whom you doubtless report, who is forever making judgements and takes no pleasure in his job. > > - Christopher
From: spinoza1111 on 12 Jun 2005 07:51 CBFalconer wrote: > spinoza1111(a)yahoo.com wrote: > > > ... snip ... > > > > 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. > > Showing total non-comprehension of the meaning of O notation. Showing either that total non-comprehension of O notation, or worse, the inability to program in contexts where it makes sense to pragmatically reduce execution time within a given order. I say it doesn't transform n^2, it reduces within that level. I have to conclude that your comprehension is at best that of a mere examination-passer or deficient. > > -- > "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 Thompson
From: CBFalconer on 12 Jun 2005 16:00
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. > > 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'. > > 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. -- "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 |