Average-case complexity: Difference between revisions

Revision as of 11:25, 5 May 2014

Revision as of 21:29, 19 May 2014

Line 23:

</math>

for every n, t, for some &epsilon; > 0 and polynomial p, where t_A(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>