Re: puzzle

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.

--
pete
.

Relevant Pages

  • Re: puzzle
    ... pete wrote: ... N/2 the time on average it finds U. ... The resentment here is of ability to explain, ...
    (comp.programming)
  • Re: puzzle
    ... > pete wrote: ... is further away from Othan a O) algorithm would be. ... Prev by Date: ...
    (comp.programming)
  • Re: puzzle
    ... snip ... ... > You're doing Osearches, times a linearly shrinking array, only ... N/2 the time on average it finds U. ... "If you want to post a followup via groups.google.com, ...
    (comp.programming)
  • Simple proof
    ... n can be written as the sum of two ... numbers in n/2 ways, without repetition. ... Prev by Date: ...
    (sci.math)