playbooks

home / skills / a5c-ai / babysitter / amortized-analysis-assistant

amortized-analysis-assistant skill

/plugins/babysitter/skills/babysit/process/specializations/domains/science/computer-science/skills/amortized-analysis-assistant

This skill helps you perform amortized analysis across data structures by applying aggregate, accounting, and potential methods to derive bounds and

npx playbooks add skill a5c-ai/babysitter --skill amortized-analysis-assistant

Review the files below or copy the command above to add this skill to your agents.

Files (1)
SKILL.md
1.1 KB
---
name: amortized-analysis-assistant
description: Apply amortized analysis techniques including aggregate, accounting, and potential methods
allowed-tools:
  - Bash
  - Read
  - Write
  - Edit
  - Glob
  - Grep
metadata:
  specialization: computer-science
  domain: science
  category: algorithm-analysis
  phase: 6
---

# Amortized Analysis Assistant

## Purpose

Provides expert guidance on amortized analysis of data structures and algorithms using multiple analysis techniques.

## Capabilities

- Aggregate method calculations
- Accounting method with credit tracking
- Potential function design and verification
- Banker's method for persistent data structures
- Generate amortized bounds documentation
- Handle complex operation sequences

## Usage Guidelines

1. **Method Selection**: Choose appropriate amortized analysis method
2. **Potential Design**: Design potential function for potential method
3. **Credit Tracking**: Track credits for accounting method
4. **Bound Derivation**: Derive amortized cost bounds
5. **Documentation**: Generate clear analysis documentation

## Tools/Libraries

- Symbolic computation
- LaTeX documentation
- Proof assistants

Overview

This skill helps engineers and researchers perform amortized analysis on data structures and algorithm sequences using aggregate, accounting, and potential techniques. It produces step-by-step derivations, tracks credits, and proposes potential functions to justify amortized bounds. The goal is clear, verifiable amortized-cost documentation you can reuse in proofs or code reviews.

How this skill works

You provide the sequence of operations, cost model, and any invariants or initial conditions. The skill applies the chosen technique—aggregate sums, accounting with explicit credit assignments, or potential functions—to compute amortized costs and verify nonnegativity of potentials. It can also suggest banker's-style credit rules for persistent structures and produce formalized documentation of the resulting bounds.

When to use it

  • Evaluating performance of dynamic arrays, splay trees, union-find, and other amortized structures.
  • Designing credit assignments or potential functions when worst-case analysis is too pessimistic.
  • Comparing alternative implementations by their amortized cost per operation.
  • Preparing proofs for papers, lectures, or code reviews that require rigorous amortized bounds.
  • Verifying amortized guarantees for persistent or partially-persistent data structures.

Best practices

  • Start with a clear cost model and list of primitive operations before choosing a technique.
  • Use the aggregate method for simple repeated patterns, accounting for tricky sequences with the accounting method.
  • Design potential functions to reflect stored work; always check that potential is nonnegative and potential decreases cover actual costs.
  • Document assumptions (initial potential, invariants) and show a per-operation charging argument for reproducibility.
  • Keep analyses modular: analyze substructures independently and compose bounds when possible.

Example use cases

  • Derive O(1) amortized time for dynamic array append with occasional resizing using aggregate and accounting methods.
  • Design a potential function to prove O(log n) amortized time for splay tree operations across access sequences.
  • Assign credits to operations in a union-find implementation to show near-constant amortized union/find costs.
  • Generate LaTeX-ready documentation of an amortized proof for inclusion in academic papers or design docs.

FAQ

Can the skill verify that a potential function is valid?

Yes. It checks nonnegativity and that decreases in potential plus amortized charges cover actual costs across the provided operation sequences.

Does it produce human-readable proofs?

It generates clear stepwise derivations and can format results for LaTeX or documentation, suitable for proofs, lectures, or code reviews.