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