Assume that I have two lists named a and b, and I want to assign slice b[j:j len2] with len2 elements to slice a[i:i len1] with len1 elements, what's the time complexity of this operation?

a[i:i len1] = b[j:j len2]

CodePudding user response：

If len1 == len2 then it's O(len1) because it's equivalent to the loop:

for n in range(len1):
    a[i n] = b[j n]

But if the lengths are different, the elements after the slice in a have to be shifted to open or close the space required for the b slice. And if the list is growing, it's possible that the entire list needs to be relocated to make room. This makes the worst-case complexity O(len(a) len2).

CodePudding user response：

Have a look at this wiki entry.

Slice assignment in general is considered to be O(k n), although I believe CPython has some optimizations