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

Subject: Re: [boost] [Containers] Complexity of flat_*::insert(first,last)
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-08-05 07:51:13

John Bytheway wrote:
> 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:

OK, but that's only the "first part".  (I don't know why Ion has chosen 
to break down the complexity into separate parts for each step.  As we 
all know, O(A+B) is the same as O(A) if A is always larger than B.  As 
your posts show, this causes confusion.)

To me it's fairly clear that implementing insert(range) as a simple 
loop will be O( N * (S+N) ) : you're doing N separate inserts, and each 
one will have to move on average half of the existing elements along by 
one.  A one-pass algorithm like std::inplace_merge must do much better 
than that, i.e. O(N log N + S).

FYI, the approach that I took in my equivalent class was to require the 
user to explicitly sort the container after doing inserts.  This makes 
it possible to perform efficient batch updates without a temporary 
container, at the cost of a more complex and less standard interface.

Regards,  Phil.