coq-quicksort-complexity

Proofs of Quicksort's worst- and average-case complexity. 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.

opam install coq-quicksort-complexity.8.5.0
homepage
https://github.com/coq-contribs/quicksort-complexity
license
BSD
bugs tracker
https://github.com/coq-contribs/quicksort-complexity/issues
dependencies
coq (>= 8.5 & < 8.6~)
source
https://github.com/coq-contribs/quicksort-complexity/archive/v8.5.0.tar.gz
package
https://github.com/coq/opam-coq-archive/tree/master/released/packages/coq-quicksort-complexity/coq-quicksort-complexity.8.5.0