The Running Time of += on Char Strings ?

Daniel Dittmar daniel.dittmar at sap.corp
Thu Mar 24 11:15:57 CET 2005

Edg Bamyasi wrote:
> What is the running time of conactination on character strings.
> i.e.
> is it Amortized Constant time? I don't think it would be O((number of
> chars)^2) but i really don't know.

Strings are immutable, so
is executed as
joe = joe + "99999999999999999"

This means that there is
- one allocation
- two memcpy
- one deallocation (old value of joe)

My guess is that the allocations play a rather large part in the actual 

Creating a large string by multiple concatenations is slow, instead you 
- use module cStringIO
- or add all the strings to a list and do "".join (listvariable)

How are you supposed to know? It's mostly Python folklore, some of which 
has been written down in the Python Cookbook 


More information about the Python-list mailing list