From: "Ara.T.Howard" <Ara.T.Howard@...>
Date: 2005-08-05T23:01:07+09:00
Subject: Re: algorithm help

On Fri, 5 Aug 2005, Martin DeMello wrote:

> "Kroeger Simon (ext)" <simon.kroeger.ext@siemens.com> wrote:
>> Hi robert,
>>
>>> [..snip..]
>>> This looks cute.  What makes you sure it's O(log n)?
>>
>> in fact I think its O(m * log n) with n equals the size of data and m
>> the number of ranges.
>
> Yeah, I can't prove it without handwaving, but I think O(m log n) is the
> best you can do.

i think worst case proves it:

   [1,2,3]

three ranges, ergo m, log(n) to find the ends is well proven since it's just
binary search.

regards.

-a
-- 
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| My religion is very simple.  My religion is kindness.
| --Tenzin Gyatso
===============================================================================