Time and space complexity of this particular slicing operation on lists?

user_11878985 0
Viewed 41

I have 2 lists say nums1 with n+m elements and nums2 with m elements. if I perform
nums1[n-m:] = nums2

will there be any extra space used, what is the time complexity of such operation?

space-complexity time-complexity python
1 Answers

The operation you talk about is copying m elements from num2 to num1.

It is not deep copy because:

a= [[1,1], [2,2], [3,3], [4,4]]
b=[[7, 7],[8,8]]
a[2:] = b
b[0][0] = 111

Makes a equal to [[1, 1], [2, 2], [111, 7], [8, 8]].

So the space used depends on the implementation of the interpreter (it could use an extra space to temporary copying).

But the optimal complexities for the operator's algorithm, not including the space for the lists themselves, are:

  1. Time complexity O(m)
  2. Space complexity O(1)
user_131222520
Related