Content deleted Content added
Undid revision 870301051 by Fhartykhunt (talk) |
→Definitions: ce: indenting math |
||
Line 21:
To create a more robust definition of average-case efficiency, it makes sense to allow an algorithm A to run longer than polynomial time on some inputs but the fraction of inputs on which A requires larger and larger running time becomes smaller and smaller. This intuition is captured in the following formula for average polynomial running time, which balances the polynomial trade-off between running time and fraction of inputs:
:<math>
\Pr_{x \in_R D_n} \left[t_A(x) \geq t \right] \leq \frac{p(n)}{t^\epsilon}
</math>
Line 27:
for every n, t, ε > 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>
E_{x \in_R D_n} \left[ \frac{t_{A}(x)^{\epsilon}}{n} \right] \leq C
</math>
| |||