On 19 May 2015 at 11:15, Serhiy Storchaka <storch...@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 -- https://mail.python.org/mailman/listinfo/python-list
