A Calculus for Amortized Expected Runtimes
summary
Develops a weakest-precondition-style aert calculus that composes the potential method with an extended ert for dynamic memory using runtime separation logic and signed random variables, gives invariant-based loop rules (including a novel loop rule for signed variables) and proves soundness against an operational Markov decision process with countable nondeterminism, avoids heavy integrability machinery, and applies the method to a randomized delete‑insert‑find‑any set that yields a constant amortized expected runtime per operation.
AI-written summary · about