Brian Quinlan wrote: > The fastest algorithm that I have been able to devise for doing so is: > O(n * log(len(lst))). Can anyone think or a solution with a better time > complexity? If not, is there an obviously better way to do this > (assuming n is big and the list size is small).
If list is indeed short, I'd say common sense speaks against complicating and optimizing further - you can only get log(len(lst))-fold speedup, which is in your case more or less a small constant. _IF_ this part of code later turns out to be a bottleneck, you might profit more by porting it to C than searching for an O(n) solution, if it even exists. -- http://mail.python.org/mailman/listinfo/python-list
