TRT
Sign in

Expert · Module 22 · Lesson 2 of 4

Accounting and potential methods

The accounting method overcharges cheap operations and saves the surplus as credit for expensive ones. The potential method does the same with a single function of the structure's state. Both prove amortized bounds when simply adding up costs is hard.

Pro — members onlyAbout 15 minutes

By the end you can

  • Prove an amortized bound with the accounting method, by assigning charges and showing credit never goes negative
  • Define a potential function and compute amortized costs as actual cost plus change in potential
  • Apply both methods to a queue built from two stacks and to dynamic arrays

Builds on Amortized analysis.

01 · A question first

A queue built from two stacks occasionally moves its whole contents from one stack to the other. Counting exactly when those moves happen, over every possible mix of pushes and pops, is tedious. Instead, imagine each push pays a little extra into a savings account. If the account never runs dry, the bound is proved. How much should each push pay?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • When adding up is hard
  • The accounting method
  • The potential method
  • Doubling, again
  • Choosing a potential
  • Shrinking without thrashing
  • Why these methods matter
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeDesign a stack with increment operationSupport push, pop and adding a value to the bottom k elements, all in O(1), by recording increments lazily and passing them down on pop.Practice · easy · LeetCodeImplement queue using stacksBuild a FIFO queue from two LIFO stacks, and show that each operation is O(1) amortized.

Asked in interviews

Something wrong with this lesson? Report a problem