How to identify which numbers in a list are within each others' range
arnodel at googlemail.com
Fri Feb 1 22:13:59 CET 2008
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).
More information about the Python-list