From: Eric Ford (eford_at_[hidden])
Date: 2001-07-04 02:14:45
--- In boost_at_y..., "Sofus Mortensen" <list_at_l...> wrote:
> I think it is better than O( log(n) ). Finding the range shouldn't
> more than O( log(l ) ), where l is the distance between the guess
> sought element. Searching the range is O( log(l) ) too, since the
> will have no more than l elements.
Sure. It's O(log(n)) worst case (l~n), O(1) best case (l~1).
Actually for equals_range, the lower limit to the order is set by the
size of the range found.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk