for every n, t, ε > 0 and polynomial p, where t<sub>A</sub>(x) denotes the running time of algorithm A on input x, and ε is a positive constant value.<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>
Line 31:
</math>
for some constantconstants C and ε, where n = |x|.<ref name="ab09">S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009.</ref> In other words, an algorithm A has good average-case complexity if, after running for t<sub>A</sub>(n) steps, A can solve all but a <math>\frac{n^c}{(t_A(n))^{\epsilon}}</math> fraction of inputs of length n, for some ε, c > 0.<ref name="bog06"/>
