>On Mon, Jun 16, 2008 at 4:34 AM, Bart Kastermans <bk******@gmail.comwrote:It will depend what version of Python you're using and the *exact* details>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/0...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.
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