String Concatenation O(n^2) (was: Re: Explaining Implementing a Binary Search Tree.)
ian.g.kelly at gmail.com
Mon Jun 16 18:41:05 CEST 2008
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
> 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
> 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. Remember that the copy code uses memcpy from
the C library, though, so it's quite fast. If you're not seeing it
for relatively small strings, it's probably that the major time
component is the Python looping construct, not the copy operation.
I tried it at lengths of multiples of 10, and it remained linear up
until 1E6. At 1E7, it appears to turn quadratic. I tried 1E8, but it
hasn't finished yet. I expect it to take the better part of an hour.
>>> from timeit import Timer
>>> a = Timer("a += 'a'", "a = ''")
Even though it doesn't become quadratic until 1E7, it's still up to an
order of magnitude faster to use str.join for smaller strings, though:
>>> b = Timer("''.join(['a'] * 1000000)")
More information about the Python-list