How to identify which numbers in a list are within each others' range

[Arnaud Delobelle]

On Feb 1, 8:34 pm, "Neil Cerutti" <mr.ceru... at gmail.com> wrote:
> On Feb 1, 2008 3:16 PM, Arnaud Delobelle <arno... at googlemail.com> wrote:

> > The total number of iterations is 1+2+...+n = n(n+1)/2 (when n is the
> > number of intervals) so this has quadratic behaviour regardless of
> > input.[...]
> But it breaks out of the inner loop as soon as ranges on the right
> cannot overlap. The loop is O(N) for all input if I define N as
> "number of overlaps", a pretty reasonable definition--it's madness to
> expect to report N overlaps with less than N complexity.
>
> Unless I'm making a silly mistake. Again.

No you're not mistaken, I am.  I didn't see the 'else: break' bit
which of course makes all the difference.  Sorry...

On the point of complexity though, it is only O(N) is N dominates
nlogn (n being the length of input).

--
Arnaud