Marc-Andre Lemburg <m...@egenix.com> added the comment: Tim Peters wrote: > > Tim Peters <tim.pet...@gmail.com> added the comment: > > [Marc-Andre] >> BTW: I wonder how long it's going to take before >> someone figures out that our merge sort based >> list.sort() is vulnerable as well... its worst- >> case performance is O(n log n), making attacks >> somewhat harder. > > I wouldn't worry about that, because nobody could stir up anguish > about it by writing a paper ;-) > > 1. O(n log n) is enormously more forgiving than O(n**2). > > 2. An attacker need not be clever at all: O(n log n) is not only > sort()'s worst case, it's also its _expected_ case when fed randomly > ordered data. > > 3. It's provable that no comparison-based sorting algorithm can have > better worst-case asymptotic behavior when fed randomly ordered data. > > So if anyone whines about this, tell 'em to go do something useful instead :-)
Right on all accounts :-) ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue13703> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
