472,378 Members | 1,648 Online

# 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 11144
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 thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 3 by: Edg Bamyasi | last post by: This Is A Late Cross Post from comp.lang.python. It seems the mistery is deeper then i expected. What is the running time of conactination on character strings. i.e. >> joe="123" >>... 4 by: GiriT | last post by: Would appreciate some insight into how people are dealing with the implicit conversion of timezones that .NET does. If a server in one timezone delivers up a typed dataset to a component in... 12 by: pjhyett | last post by: standard 2d array filling with increasing numbers for rows and columns: for(int i=0;i mFifo; But,... 1 by: dondora | last post by: hi there. this is my homework. I've been trying to get some result but things haven't been gone well. Those are the nested loop. And What I have to do is to get time complexity T(n) of the nested... 10 by: WebCM | last post by: There is a function: http://paste.ubuntu.com/21865 It needs GMT date in YYYY-MM-DD HH:MM:SS format - in SQL: datetime. If date is the same as today, the function returns "Today". There is one... 2 by: Kemmylinns12 | last post by: Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and efficiency. While initially associated with cryptocurrencies... 0 by: antdb | last post by: Ⅰ. Advantage of AntDB: hyper-convergence + streaming processing engine In the overall architecture, a new "hyper-convergence" concept was proposed, which integrated multiple engines and... 0 by: WisdomUfot | last post by: It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific technical details, Gmail likely implements measures... 0 by: Oralloy | last post by: Hello Folks, I am trying to hook up a CPU which I designed using SystemC to I/O pins on an FPGA. My problem (spelled failure) is with the synthesis of my design into a bitstream, not the C++... 0 by: Carina712 | last post by: Setting background colors for Excel documents can help to improve the visual appeal of the document and make it easier to read and understand. Background colors can be used to highlight important... 0 by: Rahul1995seven | last post by: Introduction: In the realm of programming languages, Python has emerged as a powerhouse. With its simplicity, versatility, and robustness, Python has gained popularity among beginners and experts... 2 by: Ricardo de Mila | last post by: Dear people, good afternoon... I have a form in msAccess with lots of controls and a specific routine must be triggered if the mouse_down event happens in any control. Than I need to discover what... 1 by: Johno34 | last post by: I have this click event on my form. It speaks to a Datasheet Subform Private Sub Command260_Click() Dim r As DAO.Recordset Set r = Form_frmABCD.Form.RecordsetClone r.MoveFirst Do If... 1 by: ezappsrUS | last post by: Hi, I wonder if someone knows where I am going wrong below. I have a continuous form and two labels where only one would be visible depending on the checkbox being checked or not. Below is the...