Content deleted Content added
m Replace magic links with templates per local RfC and MediaWiki RfC |
|||
Line 70:
===Sorting algorithms===
As mentioned above, much early work relating to average-case complexity focused on problems for which polynomial-time algorithms already existed, such as sorting. For example, many sorting algorithms which utilize randomness, such as [[Quicksort]], have a worst-case running time of O(n<sup>2</sup>), but an average-case running time of O(nlog(n)), where n is the length of the input to be sorted.<ref name="clrs">Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. {{ISBN
===Cryptography===
| |||