From: Joel VanderWerf <vjoel@...>
Date: 2005-08-02T14:18:31+09:00
Subject: Re: algorithm help

Daniel Amelang wrote:
> Instead of looking for ranges, why not look for gaps in the sequence
> as you read in the input. Keep track of where each gap occurs
> (beginning and end), like an inverse range. If you do this as you
> populate your array, you won't have to go back and traverse the array
> afterwards (hence the O(n)).

It's already O(n) if you read the array sequentially. I guess we're
assuming the array is given as a block of memory somewhere (Ara said
something about mmap...), so if we're clever enough we may not need to
traverse it even once.

> Hmmm...you would have thought about that by now if it were _that_ easy :)
> 
> Sorry, Ara, I guess I don't fully understand your problem.
> 
> Dan
> 


-- 
      vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407