4 Aug
2011
4 Aug
'11
7:24 p.m.
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:
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.
John