Content deleted Content added
m Reverted edits by 152.26.62.217 (talk) to last version by Dawnseeker2000 |
Adamant.pwn (talk | contribs) →Table of common time complexities: For AKS test size of the input is log n, not n. |
||
Line 28:
| logarithmic time || [[DLOGTIME]] || ''O''(log ''n'') || log ''n'', log(''n''<sup>2</sup>) || [[Binary search]]
|-
| polylogarithmic time || || poly(log ''n'') || (log ''n'')<sup>2</sup> ||
|-
|fractional power || || {{math|''O''(''n''<sup>c</sup>)}} where {{Math|0 < c < 1}} || ''n''<sup>1/2</sup>, ''n''<sup>2/3</sup> || Searching in a [[kd-tree]]
Line 42:
| cubic time || || ''O''(''n''<sup>3</sup>) || ''n''<sup>3</sup> || Naive multiplication of two ''n''×''n'' matrices. Calculating [[partial correlation]].
|-
| polynomial time || [[P (complexity)|P]] || 2<sup>''O''(log ''n'')</sup> = poly(''n'') || ''n''{{sup|2}} + ''n'', ''n''<sup>10</sup> || [[Karmarkar's algorithm]] for [[linear programming]]; [[AKS primality test]]<ref name="tao-aks">{{cite book|title=An epsilon of room, II: Pages from year three of a mathematical blog|last=Tao|first=Terence|publisher=American Mathematical Society|year=2010|isbn=978-0-8218-5280-4|series=Graduate Studies in Mathematics|volume=117|___location=Providence, RI|pages=82–86|contribution=1.11 The AKS primality test|doi=10.1090/gsm/117|mr=2780010|authorlink=Terence Tao|contribution-url=https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/}}</ref><ref>{{cite paper|last1=Lenstra|first1=Jr., H.W.|author1-link=Hendrik Lenstra|last2=Pomerance|first2=Carl|author2-link=Carl Pomerance|date=11 December 2016|title=Primality testing with Gaussian periods|url=https://math.dartmouth.edu/~carlp/aks111216.pdf}}</ref>
|-
| quasi-polynomial time || QP || 2<sup>poly(log ''n'')</sup> || ''n''<sup>log log ''n''</sup>, ''n''<sup>log ''n''</sup> || Best-known O(log<sup>2</sup> ''n'')-[[approximation algorithm]] for the directed [[Steiner tree problem]].
| |||