Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Amortisation — where it appears

Spreading the cost of an occasional expensive operation over the cheap ones around it, so that a sequence has a low average cost even though one step in it is dear. The average is a real guarantee only when the sequence it is averaged over actually happens.

Named by 4 essays across 3 fields — each of them below, with the objects they name alongside it.

50%60%70%80%90%100%0%1%2%5%10%25%50%share of keys arriving latemean leaf filleven splitsrightmost-split rulesibling first, two into threeln 2131,072 keys, leaves of 64late keys arrive at a random later point

The sibling a full leaf asks first

The rule databases use to fix ascending inserts fills their leaves completely and collapses to 53.4% when one key in a hundred arrives late. A leaf that offers a key to a sibling before it splits, and splits two full leaves into three when neither will take one, holds 84.2% on the same stream — and is better with a trickle of late keys than without one, because a perfectly ascending stream has no sibling with room.

applied · Transfer 0.01%0.1%1%10%100%4,00012,00020,00028,00036,00044,00052,00060,000keys insertedabsent keys answered yesfingerprints, none reserved1 bit longer a doubling2 bits longer a doublingfingerprints, 5 reservedforecast 2,000, target 1.0%; dotted: the forecastdashed: the target rate

The bits given to the wrong keys

A fingerprint table that gives later arrivals longer fingerprints holds 3.6% where a table that reserves nothing holds 21.1%, and it never runs out of reserve because it has none. It also dies at exactly the same size as the table that reserved nothing — 32 times its forecast, on the same key — because every generation shares one quotient, and the generation with the shortest fingerprint is the one that arrived first.

randomness · Randomness 0396,049792,0981,188,1481,584,1970326496128queries answeredcounted work, cumulativebreak-even at 2.7 queriesBellman–Ford from each sourceone reweighting, then Dijkstra256 vertices, 2,009 arcsanswers compared entry by entry

How long a reweighting stays true

Johnson's one Bellman–Ford run costs under one per cent of an all-pairs computation because it is divided over every source. Asked one query at a time it is divided over nothing, and it still repays itself after 2.7 queries — because the preparation is one Bellman–Ford and every query saves a third of another. What decides the trade is not the query count but whether the graph holds still: at half a per cent of arcs redrawn between queries the stored potential is worth exactly nothing, and its life is geometric at a per-arc failure rate of 6.6%.

graphs · Graph 00.50011.50arcs redrawn between queriesstored potential ÷ Bellman–Ford per query0.02%0.1%0.5%2%5%20%recomputed from nothingmended from the broken arcs256 vertices, 128 queriesarc costs redrawn

A potential mended where it broke

A stored reweighting on a 256-vertex graph with negative arcs costs 10,045 relaxations to rebuild, and rebuilding it every time an update breaks it stops paying once half a per cent of arcs change between queries. Mending it from the arcs that broke costs 16 to 442 relaxations instead, and the stored potential stays at two thirds of the per-query cost at every rate of change. When the change is a vertex whose costs all move together, a repair reaches nearly every vertex. It still costs a third of a rebuild.

graphs · Graph

Named alongside it

The objects these essays reach for when they reach for this one.

Space time tradeBreak-evenDesign parameterDynamic graphInvalidationNegative weightPotential functionReweightingShortest pathApproximate membershipB-treeBellman–Ford

All concepts