On Mon, 16 Jun 2008 10:41:05 -0600, Ian Kelly <[EMAIL PROTECTED]> wrote:
On Mon, Jun 16, 2008 at 4:34 AM, Bart Kastermans <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
