How expensive are list and tuple slicing?

[Tim Peters]

[Alex]
> Does slicing a list allocate memory at the point of the slice, or does
> python implement some sort of copy on write scheme to save memory?  How
> about tuples (which are immutable)?

Same answer for both:  x[i:j] takes time and space proportional to j-i; a
new and independent object is created.

> Example: The following snippet of code counts the number of items in a
> sequence.  It is obviously a very stupid way of doing this.  Neither the
> sequence, nor any of its slices, are ever modified.

Doesn't matter.

> How much memory does it consume if the sequence is a list?

Proportional to len(sequence)**2.

> A tuple?

The same, but with a smaller proportionality constant because an N-element
tuple requires a little less space than an N-element list in CPython.

> Is the behavior the same on Python and Jython?

Pretty much, yes.

> def count(sequence):
>   if len(sequence)==1:
>     return 1
>   return count(sequence[:1])+ count(sequence[1:])

The "count(sequence[:1])" part doesn't contribute to the quadratic growth.