Time Complexity of String Operations
dwahler at gmail.com
Tue Jul 22 06:39:58 CEST 2008
On Mon, Jul 21, 2008 at 10:31 PM, youtoo <you2000too at gmail.com> wrote:
> It has been extensively discussed the time complexity (quadratic) of
> string concatenation (due to string's immutability).
Actually, it is roughly linear, at least for reasonable string lengths:
$ python -V
$ python -mtimeit -s "n=1000; a='#'*n" "a+a"
1000000 loops, best of 3: 1 usec per loop
$ python -mtimeit -s "n=10000; a='#'*n" "a+a"
100000 loops, best of 3: 5.88 usec per loop
$ python -mtimeit -s "n=100000; a='#'*n" "a+a"
10000 loops, best of 3: 59.8 usec per loop
Repeatedly constructing a string by appending a constant number of
characters at a time, however, is quadratic in the final string length
(although VM optimizations may affect this).
> But what is:
> == the time complexity of string indexing? Is it constant?
> == the time complexity of string slicing? Is it O(K) with K the
> slice's length?
I suspect so, since the time is dominated by the time taken to copy
the data into a new string object.
> How are strings stored in Python? As arrays? As linked lists?
Arrays; see Include/stringobject.h in the Python source distribution.
More information about the Python-list