### Abstract

A framework for the analysis of the amortized complexity of functional data structures is formalized in Isabelle/HOL and applied to a number of standard examples and to the folowing non-trivial ones: skew heaps, splay trees, splay heaps and pairing heaps.

### License

BSD License

### History

July 14, 2016
  Moved pairing heaps from here to the new Pairing_Heap
July 12, 2016
  Moved splay heaps from here to Splay_Tree
March 17, 2015
  Added pairing heaps by Hauke Brinkop.

### Topics

- Computer science/Data structures

### Related publications

- Nipkow, T., & Brinkop, H. (2018). Amortized Complexity Verified. Journal of Automated Reasoning, 62(3), 367–391. https://doi.org/10.1007/s10817-018-9459-3
- Author's copy
- Wikipedia

### Session Amortized_Complexity

- Amortized_Framework0
- Amortized_Framework
- Amortized_Examples
- Priority_Queue_ops_merge
- Skew_Heap_Analysis
- Lemmas_log
- Splay_Tree_Analysis_Base
- Splay_Tree_Analysis
- Splay_Tree_Analysis_Optimal
- Priority_Queue_ops
- Splay_Heap_Analysis
- Pairing_Heap_Tree_Analysis
- Pairing_Heap_Tree_Analysis2
- Pairing_Heap_List1_Analysis
- Pairing_Heap_List1_Analysis2
- Pairing_Heap_List2_Analysis

### Depends on

- Pairing Heap
- Skew Heap
- Splay Tree

### Used by

- Root-Balanced Tree
- Parameterized Dynamic Tables

## Cite

×

Amortized_Complexity-AFP

    @article{Amortized_Complexity-AFP,
      author  = {Tobias Nipkow},
      title   = {Amortized Complexity Verified},
      journal = {Archive of Formal Proofs},
      month   = {July},
      year    = {2014},
      note    = {\url{https://isa-afp.org/entries/Amortized_Complexity.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Apr 18, 2020 : Isabelle2020
- Jun 11, 2019 : Isabelle2019
- Aug 16, 2018 : Isabelle2018
- Oct 10, 2017 : Isabelle2017
- Dec 17, 2016 : Isabelle2016-1
- Feb 22, 2016 : Isabelle2016
- May 28, 2015 : Isabelle2015
- May 27, 2015 : Isabelle2015
- May 19, 2015 : Isabelle2014
- Aug 28, 2014 : Isabelle2014