469,955 Members | 2,080 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,955 developers. It's quick & easy.

Time Complexity of String Operations

It has been extensively discussed the time complexity (quadratic) of
string concatenation (due to string's immutability).
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?

How are strings stored in Python? As arrays? As linked lists?

Thanks a lot!

yt.
Jul 22 '08 #1
3 10481
On Mon, Jul 21, 2008 at 10:31 PM, youtoo <yo********@gmail.comwrote:
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 2.5.2
$ 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?
Yes.
== 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.

-- David
Jul 22 '08 #2


youtoo wrote:
It has been extensively discussed the time complexity (quadratic) of
string concatenation (due to string's immutability).
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?

How are strings stored in Python? As arrays? As linked lists?
There is a Py wiki page on such issues. A wiki search should find it.

Jul 22 '08 #3

On 22 jul, 01:39, "David Wahler" <dwah...@gmail.comwrote:
On Mon, Jul 21, 2008 at 10:31 PM, youtoo <you2000...@gmail.comwrote:
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 2.5.2
$ 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?

Yes.
== 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.

-- David
Thank you very much!

yt.
Jul 22 '08 #4

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

3 posts views Thread by Edg Bamyasi | last post: by
12 posts views Thread by pjhyett | last post: by
26 posts views Thread by Lionel B | last post: by
12 posts views Thread by toton | last post: by
1 post views Thread by dondora | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.