John Bytheway wrote:
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:
OK, but that's only the "first part". (I don't know why Ion has chosen to break down the complexity into separate parts for each step. As we all know, O(A+B) is the same as O(A) if A is always larger than B. As your posts show, this causes confusion.) To me it's fairly clear that implementing insert(range) as a simple loop will be O( N * (S+N) ) : you're doing N separate inserts, and each one will have to move on average half of the existing elements along by one. A one-pass algorithm like std::inplace_merge must do much better than that, i.e. O(N log N + S). FYI, the approach that I took in my equivalent class was to require the user to explicitly sort the container after doing inserts. This makes it possible to perform efficient batch updates without a temporary container, at the cost of a more complex and less standard interface. Regards, Phil.