On Feb 1, 8:34 pm, "Neil Cerutti" <[EMAIL PROTECTED]> wrote: > On Feb 1, 2008 3:16 PM, Arnaud Delobelle <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
