Re: puzzle

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.

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?

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.

- Christopher
.

Relevant Pages

  • Re: Where is behavior AI now?
    ... regards going past the basics of intelligence. ... It's like documenting the flight path of a bird, without any understanding ... This is the same missing piece which has been missing for over 50 ... It's like trying to reverse engineer an encryption algorithm. ...
    (comp.robotics.misc)
  • Re: puzzle
    ... >> Christopher Barber wrote: ... > sometimes misuse) obscure words and to insert long paragraphs of ... given the choice between an algorithm that costs n*n steps ... > than you that would call such an algorithm "close to" O. ...
    (comp.programming)
  • 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: algorithm to sum run time of simultaenous jobs?
    ... jobs are a match for the size of the objects you're trying to fit into ... the 5 bins? ... then my understanding is that there is no algorithm outside of ...
    (rec.puzzles)
  • Re: how can i large divide?
    ... stuff and it has useful applications then that's great. ... The big O notation sounds useful if you're working with theory, ... Big O notation is what can tell you that your algorithm that's ... Yes, you can measure this kind of thing, but an understanding of ...
    (comp.lang.c)