Amortized Complexity

MaRDI QIDQ40320swMATHFDO

Authors Tobias Nipkow

Publication date 7 July 2014

Official website https://www.isa-afp.org/entries/Amortized_Complexity.html

Cites work

• A systematic analysis of splaying
• Amortized complexity verified
• Unnamed Publication
• Self-adjusting binary search trees
• Self-Adjusting Heaps
• The derivation of a tighter bound for top-down skew heaps
• The pairing heap: A new form of self-adjusting heap

Described by source

• Amortized complexity verified

Cited in

(34)

• Formalizing network flow algorithms: a refinement approach in Isabelle/HOL
• Netsoft
• ABC
• CFML
• Automatic functional correctness proofs for functional search trees
• CAMPY
• ACE
• Grail
• TiML
• Camelot
• PairingHeap
• Splay Tree
• Skew Heap
• Ergodic theory
• Separation Logic
• Flow Networks
• AVL trees
• CryptHOL
• QuickSort Cost
• Treaps
• Root Balanced Tree
• Random BSTs
• Density Compiler
• Dune
• Monad normalisation
• Probabilistic_Prime_Tests
• Prpu_Maxflow
• TcT
• KoAT
• Verified analysis of random binary tree structures
• Verified analysis of random binary tree structures
• Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits
• Amortized complexity verified
• ATLAS: automated amortised complexity analysis of self-adjusting data structures

This page was built for software: Amortized Complexity