2

Given a string s of length n, the slicing operation s[i : j] in Python 3, where
(0 <=i <= j <= n), takes how much time in Big-O notation?

Is it O(n) or O(1) or something else?

Edit

Also is there any implementation difference in slicing of a list and a string in python 3?

kumarmo2
  • 1,381
  • 1
  • 20
  • 35

1 Answers1

5

CPython implements string slicing by making a new string object containing the extracted characters. That takes time proportional to the number of characters copied, so takes time proportional to j-i (the number of characters copied).

Tim Peters
  • 67,464
  • 13
  • 126
  • 132
  • It would be really helpful if you could also provide some source of that information. Thanks – kumarmo2 Jul 19 '17 at 19:02
  • See the other answer linked to in @DYZ's comment; in the end, there's no "proof" of this short of staring at the implementation code. – Tim Peters Jul 19 '17 at 19:03
  • It makes sense, but just for confirmation there is no implementation difference of slicing in a list and a string? – kumarmo2 Jul 19 '17 at 19:04
  • And the same answer applies to list slicing, tuple slicing, bytes slicing, bytearray slicing ... – Tim Peters Jul 19 '17 at 19:05
  • 2
    @Manya: https://github.com/python/cpython/blob/d81bea6520892e0428aec61c73e0631a69db11bb/Objects/unicodeobject.c#L14027, https://github.com/python/cpython/blob/d81bea6520892e0428aec61c73e0631a69db11bb/Objects/unicodeobject.c#L12388, https://github.com/python/cpython/blob/d81bea6520892e0428aec61c73e0631a69db11bb/Objects/unicodeobject.c#L2207 – Ry- Jul 19 '17 at 19:05
  • Okay and Thanks @Tim Peters. :) – kumarmo2 Jul 19 '17 at 19:06
  • 2
    The are some minor differences between string and list, e.g. `str[:]` will return the original `str`, whereas any mutable type (e.g. list) will return a complete copy. – AChampion Jul 19 '17 at 19:07