String Concatenation O(n^2) (was: Re: Explaining Implementing a Binary Search Tree.)

[Jean-Paul Calderone]

On Mon, 16 Jun 2008 10:41:05 -0600, Ian Kelly <ian.g.kelly at gmail.com> wrote:
>On Mon, Jun 16, 2008 at 4:34 AM, Bart Kastermans <bkasterm at gmail.com> wrote:
>> This is interesting.  I had never attempted to verify a big O
>> statement
>> before, and decided that it would be worth trying.  So I wrote some
>> code to
>> collect data, and I can't find that it goes quadratic.  I have the
>> graph
>> at
>>
>> http://kasterma.wordpress.com/2008/06/16/complexity-of-string-concatenation/
>>
>> It looks piecewise linear to me.
>
>I don't think there's any question that it's quadratic.  Just look at
>the C code, and you'll see that every time you concatenate the entire
>string has to be copied.

It will depend what version of Python you're using and the *exact* details
of the code in question.  An optimization was introduced where, if the
string being concatenated to is not referred to anywhere else, it will be
re-sized in place.  This means you'll probably see sub-quadratic behavior,
but only with a version of Python where this optimization exists and only
if the code can manage to trigger it.

Jean-Paul