THE FOLD / LOOT / THE VAULT / THE BANKER
THE BANKER
amortized O(1) — the binary counter pays itself
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Amortized cost — the binary counter. Increment a binary counter and usually you flip one bit. But 0111…1 + 1 cascades: every bit flips. A single increment can cost O(log n). So is counting to n slow?
No — because the expensive increments are rare. Bit 0 flips every step, bit 1 every two, bit 2 every four… Add them up and the total number of flips to count from 0 to n is 2n − popcount(n) — strictly less than 2n. Averaged over the n increments, that is under 2 flips each: amortized O(1). The banker’s method sees it directly: when you set a bit to 1, prepay one credit coin and park it on that bit; later, when a carry flips it back to 0, that saved coin pays for the flip. Every expensive cascade is already funded.
LIT verified live: this page runs the counter and confirms the total flips equal 2n − popcount(n) exactly for every n up to 2000, and the amortized cost per increment is always below 2 (window.__banker.identityHolds && amortizedUnder2). FIG the ‘coins’ are the accounting picture; the exact flip-count identity and the sub-2 average are real.
No — because the expensive increments are rare. Bit 0 flips every step, bit 1 every two, bit 2 every four… Add them up and the total number of flips to count from 0 to n is 2n − popcount(n) — strictly less than 2n. Averaged over the n increments, that is under 2 flips each: amortized O(1). The banker’s method sees it directly: when you set a bit to 1, prepay one credit coin and park it on that bit; later, when a carry flips it back to 0, that saved coin pays for the flip. Every expensive cascade is already funded.
LIT verified live: this page runs the counter and confirms the total flips equal 2n − popcount(n) exactly for every n up to 2000, and the amortized cost per increment is always below 2 (window.__banker.identityHolds && amortizedUnder2). FIG the ‘coins’ are the accounting picture; the exact flip-count identity and the sub-2 average are real.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE VAULT, beside 3LOCK — the loot domain of stored value. Amortized analysis is a vault: cheap operations bank credit that costly ones spend. AVAN (AI) built the instrument: the cascading counter, the per-step flip spikes, the prepaid coins.
The weave: David names the seat (the store of value); I make the banking visible and the identity checkable — the odometer and flip-spikes in 1D, the counter with coins in 2D, the bit-column with its prepaid credits in 3D. The sphere is the seam. Credit: the accounting/banker’s method of amortized analysis (Robert Tarjan, 1985; CLRS).
The weave: David names the seat (the store of value); I make the banking visible and the identity checkable — the odometer and flip-spikes in 1D, the counter with coins in 2D, the bit-column with its prepaid credits in 3D. The sphere is the seam. Credit: the accounting/banker’s method of amortized analysis (Robert Tarjan, 1985; CLRS).
3 ONE DIMENSION
The flips per increment: mostly 1, occasionally a tall spike when a carry cascades. The spikes are rare enough that the running average (the flat line) sits just under 2 — the whole point of amortization.
4 TWO DIMENSIONS · INTERACTIVE
Increment the counter and watch the bits flip — a coin drops onto each bit you set, and a carry cascade spends the coins already parked there. The running total of flips stays under the 2n line, no matter how vicious the individual carries.
5 THREE DIMENSIONS + AVAN’S INVERSE
The counter’s bits as a turning column — green where a bit is 1.
AVAN’s addition (the inverse-companion): the magenta coins sit on the set bits — one prepaid credit each, waiting. Paying as you go would let a single cascade cost O(log n) in the moment. Amortization is the inverse: it time-shifts the cost backward, banking a coin at each cheap set-bit so the expensive carry, when it finally comes, spends money already earned. The worst case never actually bills the worst case — it was funded by all the easy steps before it. The green is the counter’s state; the magenta is stored past work, and the spike that looks costly is paid before it arrives.
LIT Genuine amortized analysis (accounting/banker's method; Tarjan 1985, CLRS). Verified live: the counter runs and the total flips equal 2n - popcount(n) exactly for every n up to 2000, and the amortized cost per increment is always strictly below 2 (window.__banker.identityHolds && amortizedUnder2, both true). The per-bit halving (bit i flips every 2^i steps) and the prepaid-credit invariant are exact.
FIG The 'coins' are the accounting device of the banker's method — a real proof technique, not a literal payment; the flip-count identity 2n-popcount(n) and the sub-2 amortized average are exact and computed in-page. Worst-case single-increment cost really is O(log n); amortization is about the total, shown honestly.
FIG The 'coins' are the accounting device of the banker's method — a real proof technique, not a literal payment; the flip-count identity 2n-popcount(n) and the sub-2 amortized average are exact and computed in-page. Worst-case single-increment cost really is O(log n); amortization is about the total, shown honestly.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE VAULT · David Lee Wise (ROOT0), with AVAN