---
title: "Amortised Analysis"
description: "Some operations are occasionally expensive and usually cheap, so the worst case of one call overstates the cost of a run of calls. Amortised analysis charges the rare expensive step to the many cheap "
canonical: https://lightmysky.com/learn/computing/amortised-analysis-mt_1zLrl5RKGr
source: https://lightmysky.com/learn/computing/amortised-analysis-mt_1zLrl5RKGr.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Amortised Analysis

Some operations are occasionally expensive and usually cheap, so the worst case of one call overstates the cost of a run of calls. Amortised analysis charges the rare expensive step to the many cheap ones and reports the average per operation over any sequence.

Subject: Computing · Area: Algorithms & Data Structures · Ages 19 to 21
Page: https://lightmysky.com/learn/computing/amortised-analysis-mt_1zLrl5RKGr

## Ready when they can

- Show that a dynamic array that doubles on overflow appends in constant amortised time
- Use the accounting method to place a credit on each cheap operation
- Explain why an amortised bound is a worst-case claim, not an average-case one

## Lesson: Cheap usually, rare splurge, fair average

Some operations are usually cheap and rarely costly. Judging them by the rare splurge alone overstates a long run. Amortised analysis spreads the rare costly steps across the many cheap ones and reports the average per operation over any sequence.

**Example.** Appending to a doubling array usually writes one slot. When the array fills, the next append copies all past items into a doubled home. A million appends still cost only a few million steps, not a million squared, since copies thin out as the array grows.

The accounting trick makes this exact. Each append pays three coins: one spends on the write, two sit as credit on the new slot. A resize that copies k items spends the k stored credits, so the run is prepaid.

**Tip.** An amortised bound is a worst-case promise over the whole run, not an average over random inputs. It holds for any nasty sequence you feed it.

**Recap.** Prepay rare copies with credits from cheap writes, and the average stays constant.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Hash Tables and Near-Constant Lookup](https://lightmysky.com/learn/computing/hash-tables-and-near-constant-lookup-mt_7v94MJEdmJ)
- [Geometric Series and the Sum to Infinity](https://lightmysky.com/learn/mathematics/geometric-series-and-the-sum-to-infinity-mt_HHxFOv6vXS)
- [Heaps and Priority Queues](https://lightmysky.com/learn/computing/heaps-and-priority-queues-mt_W-ofiMiXWs)

## Opens up

- [Greedy Choice and the Exchange Argument](https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV-)
- [Union-Find and Minimum Spanning Trees](https://lightmysky.com/learn/computing/union-find-and-minimum-spanning-trees-mt_zOJei4yCtr)