On Fri, Feb 7, 2014 at 2:11 PM, Tim Chase <python.l...@tim.thechases.com> wrote: > On 2014-02-06 22:00, Roy Smith wrote: >> > list does not promise better than O(1) behavior >> >> I'm not aware of any list implementations, in any language, that >> promises better than O(1) behavior for any operations. Perhaps >> there is O(j), where you just imagine the operation was performed? > > Pish...there's always O(0) which is achieved by *not* performing some > unneeded operation ;-) > > -tkc
Ooh! Ooh! I got it! class fast_list(list): def append(self,obj,randrange=random.randrange): if len(self) and randrange(len(self)): return return super().append(obj) Repeated appends to this list are amortized O(0)! ChrisA -- https://mail.python.org/mailman/listinfo/python-list