Revision as of 21:29, 19 May 2014 edit Tokenzero (talk \| contribs) Extended confirmed users 1,874 edits →Efficient Average-Case Complexity: fixed definition ← Previous edit		Revision as of 22:30, 19 May 2014 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,660 edits Undid revision 609293314 by Tokenzero (talk) no, I think all epsilon was what was intended. Also, using "some" as a mathematical quantifier is too ambiguous to be a good idea. Next edit →
Line 23: </math> for every n, t, ~~for some~~ ε > 0 and polynomial p, where t<sub>A</sub>(x) denotes the running time of algorithm A on input x.<ref name="wangsurvey">J. Wang, "Average-case computational complexity theory," Complexity Theory Retrospective II, pp. 295-328, 1997.</ref> Alternatively, this can be written as <math>

Average-case complexity: Difference between revisions