From: Martin DeMello <martindemello@...>
Date: 2005-08-05T20:56:07+09:00
Subject: Re: algorithm help

Robert Klemme <bob.news@gmx.net> wrote:
> 
> Hm, my alogorithm analysis is quite rusty but I believe you would have to 
> get rid of m and replace it as an expression of n; reason being that m is 
> part of the result and not part of the input.  So you probably have to 
> calculate something like an average number of range for the set of input 
> range.  Difficult without further knowledge of the data's nature.  My gut 
> guess is that for random numbers the number of ranges is rather close to n 
> so that would make O(n*log n) which doesn't exactly look better than O(n)...

Yep - the two likely cases are m = O(1) and m = O(n). In the latter
case, the linear search is definitely better (you can see it intuitively
if you consider whether it's quicker to find the end of a given range by
crawling forward or by bouncing around - if m = O(n) the size of a given
range is roughly O(1)).

martin