Re: [boost] [Containers] Complexity of flat_*::insert(first,last)

Subject: Re: [boost] [Containers] Complexity of flat_*::insert(first,last)
From: John Bytheway (jbytheway+boost_at_[hidden])
Date: 2011-08-04 15:24:25

On 04/08/11 18:29, Phil Endecott wrote:
> Hi John,
> 
> John Bytheway wrote:
>> No; the existing complexity is better.  Let S=size() and N=aS.  You
>> have
>> 
>> N log(S+N)
> 
> Sorry, I'm lost already.  What is N log(S+N) supposed to be the 
> complexity of?

It's what Ion said two posts ago:

> I took the first part from SGI documentation (the standard also says
> "N log(a.size() + N)") since I was implementing it as a loop of
> simple insertions:
> 
> http://www.sgi.com/tech/stl/MultipleAssociativeContainer.html
> 
> Average complexity for insert range is at most O(N * log(size() +
> N)), where N is j - i.

John