String slicing big O

Question

for i in range(n):
    print("HelloWorld"[i:])

Is this O(n) or should I count the slicing as running over the characters of "HelloWorld"?

Also, when I compare two strings s1==s2 does this operation run over each letter in s1 and compare it with each letter of s2 so O(max(len(s1),len(s2))?

Linear with respect to what? String length or slice size? – cs95 Jan 17 '18 at 11:32 — cs95, Jan 17 '18 at 11:32
The string's length – Programmingfreak Jan 17 '18 at 11:34 — Programmingfreak, Jan 17 '18 at 11:34
Then, no, I don't believe it is linear. – cs95 Jan 17 '18 at 11:34 — cs95, Jan 17 '18 at 11:34

Andrew Jaffe · Answer 1 · 2018-01-17T15:36:35.377

3

In general, the indexing operation would depend on the way that the string is stored. In most cases, it is just a sequence of characters, each the same length, so indexing can be done in a single operation — hence, O(1) — by directly accessing the nth character.

However, in some cases, indexing may be more expensive; for example, some unicode strings can have characters of different sizes, in which case the only way to find character n is to start from the beginning and add up the individual character sizes, in which case it really is O(n).

All together, we then have to add n of those individual operations as we do for i in range(n), which gives another factor of n — note that this is the case even though for the second case it's O(1+2+3+4+...+n) which is O(n^2) since the sum is n*(n+1)/2. (In this case, you would probably use a somewhat different algorithm to still be able to perform this task in O(n), if efficiency is important.)

edited Jan 17 '18 at 15:36

answered Jan 17 '18 at 11:41

Andrew Jaffe

26,554
4
50
59

Note that `[i:]` is a slice not an index. – John Kugelman Jan 17 '18 at 15:46
Yes, but its complexity is just that of finding the location of character `i`. – Andrew Jaffe Jan 17 '18 at 15:52
1

Are you sure? [`str` slices, in general, copy... `str` do not slice by referencing a view of a subset of the data.](https://stackoverflow.com/a/35181399/68587) – John Kugelman Jan 17 '18 at 16:05
Yes, that seems to be the case, for understandable but slightly annoying reasons (in this case, at least). – Andrew Jaffe Jan 18 '18 at 09:39

John Kugelman · Answer 2 · 2018-01-17T16:07:36.730

0

String slicing is an O(k) operation where k is the size of the slice. That makes your program O(n²) since the slice sizes are n/2 on average.

Equality is O(min(len(s1), len(s2))). min not max. Once it hits the end of either string it's done.

edited Jan 17 '18 at 16:07

answered Jan 17 '18 at 15:44

John Kugelman

349,597
67
533
578

String slicing big O

2 Answers2