For deterministic algorithms, the average-case complexity (expected time complexity), associates a given input distribution with the expected time of an algorithm.
The literature of average case complexity includes the following work:
- Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby. On the theory of average case complexity. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 204–216. ACM, 1989.
- B. Selman D. Mitchell and H. Levesque. Hard and easy distributions of SAT problems. In Proceedings of the 10th National Conference on Artificial Intelligence, pages 459–465, 1992.
- John Franco. On the probabilistic performance of algorithms for the satisfiability problem. Information Processing Letters, 3:103–106, 1986.
- Philippe Flajolet and J.S. Vitter. Average-case analysis of algorithms and data structures. Technical report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France, August 1987.
- Yuri Gurevich. Average case completeness. Journal of Computer and`System Sciences, 42:346–398, 1991.
- Leonid Levin. Average case complete problems. SIAM J. Comput., 15:285–286, 1986.
- Rüdiger Reischuk and Christian Schindelhauer. Precise average case complexity. In 10th Annual Symposium on Theoretical Aspects of Computer Science, pages 650–661, 1993.
- Rainer Schuler and Tomoyuki Yamakami. Structural average case complexity. In Foundations of Software Technology and Theoretical Computer Science, pages 128–139. Springer-Verlag Lecture Notes in Computer Science #652, 1992.
- R. Venkatesan and S. Rajagopalan. Average case intractability of matrix and Diophantine problems. In 24th Annual ACM STOC, pages 632–642, May 1992.
- Jim Cox, Lars Ericson, Bud Mishra. "The average case complexity of multilevel syllogistic", New York University, 1995
See also
 | This computer science article is a stub. You can help Wikipedia by expanding it. |