Probabilistic analysis of algorithms

In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs. This assumption is then used to design an efficient algorithm or to derive the complexity of a known algorithms.

This approach is not the same as that of probabilistic algorithms, but the two may be combined.

For non-probabilistic, more specifically, for deterministic algorithms, the most common types of complexity estimates are

the average-case complexity (expected time complexity), in which given an input distribution, the expected time of an algorithm is evaluated
the almost always complexity estimates, in which given an input distribution, it is evaluated that the algorithm admits a given complexity estimate that almost surely holds.

In probabilistic analysis of probabilistic (randomized) algorithms, the distributions or averaging for all possible choices in randomized steps are also taken into an account, in addition to the input distributions.

Average case complexity

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.
L. Levin. Average case complete problems. SIAM J. Comput., 15:285–286, 1986.
R¨udiger 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

Average case complexity

See also