Re: puzzle

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)!

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
.