Slices time complexity

[Oscar Benjamin]

On 19 May 2015 at 11:15, Serhiy Storchaka <storchaka at gmail.com> wrote:
> On 19.05.15 12:45, Steven D'Aprano wrote:
>>
>> On Tuesday 19 May 2015 05:23, Mario Figueiredo wrote:
>>>
>>>  From the above link it seems slices work in linear time on all cases.
>>
>>
>> I wouldn't trust that is always the case, e.g. deleting a contiguous slice
>> from the end of a list could be O(1).
>
> It always has linear complexity. You need to decref removed elements.

It has linear complexity in the length of the removed slice but not in
the length of the list. So deleting k elements from the end of a list
of length N is O(k) rather than O(N) which could be a big difference.
An algorithm that repeatedly deletes slices from the end until the
entire list was gone would still be O(N) whereas one that deletes from
the beginning would probably be O(N**2).

--
Oscar