Python complexity of slice combined with asterisk for tuples-CodePudding

what is the complexity of the following example:

tuple_ = (1,2,..,3,1) # tuple of length n
(*tuple_[:k], *tuple_[k 1:]) # deleting element at index k

Normally the slicing is O(k) and O(n-k) for tuple_[:k] and tuple_[k 1:] respectively. but does the slicing first occur and then the elements are added one by one to the resulting tuple meaning another n operations? I know that the complexity is O(2n) is just O(n) but I would like to know if the number of operations is doubled here because of the asterisk?

CodePudding user response：

Suppose we have an input:

tuple_ = tuple(range(1000))
k = 400

Let's analyze 2 expressions: (tuple_[:k], tuple_[k 1:]) and (*tuple_[:k], *tuple_[k 1:]) using dis module to discover and compare what significant operations are performed under the hood.

Expression #1:

import dis

...
dis.dis("(tuple_[:k], tuple_[k 1:])")

 1           0 LOAD_NAME                0 (tuple_)
              2 LOAD_CONST               0 (None)
              4 LOAD_NAME                1 (k)
              6 BUILD_SLICE              2
              8 BINARY_SUBSCR
             10 LOAD_NAME                0 (tuple_)
             12 LOAD_NAME                1 (k)
             14 LOAD_CONST               1 (1)
             16 BINARY_ADD
             18 LOAD_CONST               0 (None)
             20 BUILD_SLICE              2
             22 BINARY_SUBSCR
             24 BUILD_TUPLE              2
             26 RETURN_VALUE

The significant operations here are BUILD_SLICE 1, BUILD_SLICE 2 and BUILD_TUPLE which gather up the running time of the expression to O(k) O(n - (k 1)) O(2)(as the final tuple BUILD_TUPLE contains only 2 slices/tuples).

Expression #2:

dis.dis("(*tuple_[:k], *tuple_[k 1:])")

  1           0 BUILD_LIST               0
              2 LOAD_NAME                0 (tuple_)
              4 LOAD_CONST               0 (None)
              6 LOAD_NAME                1 (k)
              8 BUILD_SLICE              2
             10 BINARY_SUBSCR
             12 LIST_EXTEND              1
             14 LOAD_NAME                0 (tuple_)
             16 LOAD_NAME                1 (k)
             18 LOAD_CONST               1 (1)
             20 BINARY_ADD
             22 LOAD_CONST               0 (None)
             24 BUILD_SLICE              2
             26 BINARY_SUBSCR
             28 LIST_EXTEND              1
             30 LIST_TO_TUPLE
             32 RETURN_VALUE

Here Python builds an empty list from the start with BUILD_LIST. Several reasons for that: 1) the unpacking requires flattening a sequence; 2) not all arguments might need to be unpacked, so the flattening can be arranged on different points on the final container. Knowing that tuple is immutable, the list is used as internal storage.

The significant operations here are BUILD_SLICE 1, LIST_EXTEND 1, BUILD_SLICE 2, LIST_EXTEND 2 and LIST_TO_TUPLE. Those gather the running time of the expression to O(2k) O(2(n - (k 1))) O(n)

The complexity seems quite representative.