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

Subject: Re: [boost] [Containers] Complexity of flat_*::insert(first,last)
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2011-08-04 13:32:02

El 04/08/2011 19:29, Phil Endecott escribió:
> 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?

I guess it means the number of comparisons when inserting N elements in 
a sorted vector/tree. N insertions, each one takes logarithmic 
complexity (log2(S+N) comparisons).

Ion