This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, eric.araujo, georg.brandl, gvanrossum, jcea, lemburg, pitrou, skrah, terry.reedy, tim.peters, v+python, vstinner
Date 2012-01-07.23:24:48
SpamBayes Score 1.3854115e-05
Marked as misclassified No
Message-id <1325978689.22.0.415333730698.issue13703@psf.upfronthosting.co.za>
In-reply-to
Content
[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 :-)
History
Date User Action Args
2012-01-07 23:24:49tim.peterssetrecipients: + tim.peters, lemburg, gvanrossum, barry, georg.brandl, terry.reedy, jcea, pitrou, vstinner, christian.heimes, benjamin.peterson, eric.araujo, Arfrever, v+python, alex, skrah, dmalcolm, Arach, Mark.Shannon, Zhiping.Deng, Huzaifa.Sidhpurwala, PaulMcMillan
2012-01-07 23:24:49tim.peterssetmessageid: <1325978689.22.0.415333730698.issue13703@psf.upfronthosting.co.za>
2012-01-07 23:24:48tim.peterslinkissue13703 messages
2012-01-07 23:24:48tim.peterscreate