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-03 20:41:29

On 03/08/11 22:18, Ion Gaztañaga wrote:
> El 03/08/2011 19:27, Phil Endecott escribió:
>> Hi Ion,
>>
>> (Note typo: i,j vs, first,last)
> 
> Thanks.
>>
>> What implementation are you assuming to get that complexity? It seems to
>> me that it is worse than it could be if you implement it something like
>> this (PSEUDO-CODE):
> 
> 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.
> 
> The second part is vector insertion time in case is a vector front
> insertion by N. I think it should prepend "at most ".
> 
> Your code should be:
> 
> N ¿? //insert
> + O(N log(N)) //sort (comparisons)
> + O(size()+N) //inplace_merge  (comparisons) if using intermediate memory
> 
> I think (I'm not an expert and it could depend on N's size) your code
> has lower complexity (and an additional allocation, I think it could be
> faster depending on the cost of the copies).

No; the existing complexity is better.  Let S=size() and N=aS.  You have

N log(S+N)
= aS log(S(1+a))
= S(a log(S) + a log(1+a))
< S(a log(S) + 1+2a+a log(a))

(If you don't think that's obvious see
<http://www.wolframalpha.com/input/?i=a+Log[1%2Ba]%3C1%2B2a%2Ba+Log[a]>)

= S(1+2a + a(log(S)+log(a)))
= S + aS(2 + log(aS))
= S + N(2 + log(N))
= N + N log(N) + S + N

which is the alternative.  Of course, there are constant factors to
worry about, but my gut says they work in favour of the existing
implementation too.

John Bytheway