package coq-quicksort-complexity
Proofs of Quicksort's worst- and average-case complexity
Install
Dune Dependency
Authors
Maintainers
Sources
v8.10.0.tar.gz
md5=c3b2ccbc5f13d56f46e99b51fef90a04
Description
The development contains:
- a set of monads and monad transformers for measuring a (possibly nondeterministic) algorithm's use of designated operations;
- monadically expressed deterministic and nondeterministic implementations of Quicksort;
- proofs of these implementations' worst- and average case complexity.
Most of the development is documented in the TYPES 2008 paper "A Machine-Checked Proof of the Average-Case Complexity of Quicksort in Coq", available at the homepage.
On This Page