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.

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


.

Relevant Pages

  • Re: FAQ 5.38 How do I select a random line from a file?
    ... line you've hit (by searching backwards and forwards for $/). ... The algorithm above ensures that the probability of selecting a line is precisely 1/N where N is the total number of lines in the file. ... my %linePostiion; ... but the big question is whether this costs more or less then Knuth's algorithm. ...
    (comp.lang.perl.misc)
  • Re: abstract constructor performance?
    ... >in spending a week optimising a routine that will hardly every be called. ... >used techniques with horrifying costs in space or time, ... algorithm and optimising the implementation of the algorithm. ... Thoought on the selection of an algorithm is a good plan, ...
    (comp.lang.java.programmer)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... But we have to do a lot of "playing around" with the inter-city ... costs, before such a counter-example for Diaby's Algorithm is found. ... I would like to modify my above phrase from "Diaby's Algorithm ...
    (comp.theory)
  • Re: CodeWarrior 10 on Macintel
    ... Remind me, how does this help anybody whose algorithm isn't covered by ... and it costs me less now because Apple is no longer treating ... >typos and/or dropped words render interpretation difficult for me. ...
    (comp.sys.mac.programmer.codewarrior)
  • Re: puzzle
    ... >> Christopher Barber wrote: ... >> or understanding among programming professionals. ... > algorithm "close to" O. ... bubble sort, it is almost always acceptable to use an interchange sort: ...
    (comp.programming)