Revision as of 03:08, 2 June 2025 edit OAbot (talk \| contribs) Bots 643,717 edits m Open access bot: doi updated in citation with #oabot. ← Previous edit		Revision as of 18:09, 3 June 2025 edit undo Headbomb (talk \| contribs) Edit filter managers, Autopatrolled, Extended confirmed users, Page movers, File movers, New page reviewers, Pending changes reviewers, Rollbackers, Template editors 473,137 edits ce Next edit →
Line 8: ==History and background== The average-case performance of algorithms has been studied since modern notions of computational efficiency were developed in the 1950s. Much of this initial work focused on problems for which worst-case polynomial time algorithms were already known.<ref name="bog06">{{Cite journal \|last1=Bogdanov \|first1=Andrej \|last2=Trevisan \|first2=Luca \|date=2006 \|title=Average-Case Complexity \|url=http://www.nowpublishers.com/article/Details/TCS-004 \|journal=Foundations and Trends® in Theoretical Computer Science \|language=en \|volume=2 \|issue=1 \|pages=1–106 \|doi=10.1561/0400000004 \|issn=1551-305X}}</ref> In 1973, [[Donald Knuth]]<ref name="knu73">{{cite book \| last = Knuth \| first = Donald \| title = [[The Art of Computer Programming]] \| volume = 3 \| publisher = Addison-Wesley \| date = 1973 }}</ref> published Volume 3 of the [[Art of Computer Programming]] which extensively surveys average-case performance of algorithms for problems solvable in worst-case polynomial time, such as sorting and median-finding.

Average-case complexity: Difference between revisions