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:51:00

On 04/08/11 01:41, John Bytheway wrote:
> 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]>)

Or, if you want to be paranoid about the base of the logarithm:

<http://www.wolframalpha.com/input/?i=a+Log[2%2C+1%2Ba]%3C1%2B2a%2Ba+Log[2%2C+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
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>