Chapter 16: Amortized Analysis: Accounting, Potential, and Dynamic Tables

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Ever get that feeling like you're stuck just focusing on the worst that could happen when it comes to like how fast or slow our tech runs?

Oh yeah, all the time.

Like you just sort of assume the worst case scenario.

Especially with all these complex systems out there.

Absolutely.

Focusing on just that worst case scenario can be super limiting.

Right.

Well, today we're diving into a tool that helps us see the bigger picture.

It's called amortized analysis, and it basically gives us the average performance of something over a bunch of actions, not just the absolute worst case.

Yeah, it's really about understanding the true cost over time, even when you have those occasional hiccups or slowdowns.

So instead of freaking out over one bad day, it's like figuring out your average commute time over a whole month, even with those days where traffic just goes haywire.

That's a great analogy.

Right.

And what's really cool is that it's not just an estimate or a guess.

It's like this guaranteed average, even when things get a little unpredictable.

So we're not throwing darts at a board here.

We're getting a solid idea of what to expect in the long run.

So for deep dive today, we're aiming to understand how to actually calculate this, what we might call smoothed out cost.

Smooth is a good word for it.

And we've got three main methods from our research that we're going to break down.

Aggregate analysis, the accounting method, and the potential method.

And to really make it concrete, we'll be looking at how these apply to things you might have come across before.

Stacks, specifically with a multipop operation, binary counters, and those dynamic tables that seem to resize themselves magically.

It is like magic sometimes, but hopefully less so after today.

Now I do want to point out something important for our listeners.

When we talk about charges or credits, it's really a way for us to analyze things.

Yeah, it's not actually affecting the code itself.

It's like a mental tool, you know?

More of a model to wrap our heads around this whole efficiency thing.

And the really cool part is that by understanding these techniques, we can actually design better data structures from the get go.

Oh yeah, that's the real takeaway here, leading to faster and smoother software in the long run.

Okay, so let's dive into our first method,

aggregate analysis.

What's the basic idea here?

Okay, so with aggregate analysis, we're really focused on the whole sequence of operations, not just a single one.

The big picture.

Exactly.

So let's say we perform n operations in total.

We look at the total cost, which is often written as Tn for that entire sequence, and then the magic happens.

The amortized cost for each operation is simply that total cost divided by the number of operations.

So it's like everyone shipping in equally for the whole trip, even if some folks drove more than others.

Exactly.

Like it.

Now, for our first example, let's talk about stacks.

We all know pushing and popping items are usually super fast, like 01.

Alright, those are the basics.

But one of our sources mentions this multi -pop operation.

What's that all about?

Ah, so multi -pop, often written as multi -pop, S -E -S -T -A, is basically designed to remove multiple items from the top of a stack.

So S is our stack, and K is the number of items we want to take off.

Oh yeah, so you're taking a bunch off at once.

Right.

Now, if there are fewer than K items in the stack, it just empties out the whole thing.

Makes sense.

So how long does this umtaia popi actually take?

Well, it depends on how many items are actually removed.

It's basically the minimum of the stack size, let's call that S, and that K value we talked about.

The minimum of S and K.

Got it.

So worst case scenario,

you've got a stack with, let's say, n items, and you do a multi -pop that tries to remove all of them.

Yeah.

In that case, it would take O -N time proportional to the number of items removed.

Okay, so just thinking worst case scenario here, we have n total operations, some of which could be this multi -pop that could be O -N, in the worst case.

It seems like the total time could be as bad as O -N squared, because we might be doing a linear time operation times.

That's a natural first thought, but here's where aggregate analysis gives us a different, and frankly, much more optimistic perspective.

Okay, let's hear it.

What's the catch?

Think about this.

Every item can only be popped from the stack once for every time it was pushed onto the stack.

Even with multi -pop, an item can't just magically appear on the stack to be removed.

It has to be pushed on there first.

Oh, I see where you're going with this.

So if we have n total operations, we can't possibly have done more than in push H operations.

Exactly.

And since each item can only be popped once for each time it was pushed, the total number of pops across all our operations, including those done within multi -pops, is also at most n.

So we're limited by how many we push in the first place.

Precisely.

So even though one multi -pop might take a while, the total time spent on all the push H, POP, and multi -pop operations together is limited to O -N.

Because we just can't pop more things than we've pushed.

So the amortized cost per operation becomes O -N divided by n, which is simply O -1.

A constant average cost per operation.

Much better than that scary O -N squared we were worried about initially.

That's amazing.

But I love how aggregate analysis paints a much brighter picture.

Now let's switch gears to our second aggregate analysis example.

Incrementing a binary counter.

Okay, great.

Imagine we have a k -bet counter, starting at zero.

We perform an increment operation.

What's the cost of that single operation?

So the cost of one increment is basically the number of bits that flip to represent that next value.

Flips meaning they go from zero to one or one to zero?

Yeah, exactly.

So like if you go from binary 0, 11 to 100,

three bits flip to make that happen.

Okay, so simple enough for one increment.

But the worst case is when you go from all ones to all zeros.

Oh right, because that could potentially trigger a carry to a higher bit if there's room.

Exactly.

So you might end up flipping all k -bits in that worst case.

So again, if we're only thinking worst case and we do any of these increment operations, it seems like the total cost could be as bad as a Landrace, right?

Yeah, that's what it looks like at first glance.

But once again, our research indicates that aggregate analysis shows us a more efficient reality.

Oh, it does.

Let's think about how often each bit actually changes.

Okay, I'm all ears.

The very last bit, what we call bit zero, flips every single time you increment the counter.

Right, because it's going back and forth between zero and one.

Exactly.

Now the next bit, bit one, flips every other time.

Okay, I'm starting to see a pattern here.

Bit two flips every fourth time and so on.

It's like this beautiful halving pattern.

Each bit flips half as often as the one before it.

Exactly.

So generally, bit i flips about n over 2 to the power of i in Heim's in a sequence of in increment operations.

Okay, so that frequency decreases rapidly as we move to those higher order bits.

Right.

Now to find the total number of flips over in increments, we just add up how many times each bit flips.

It's a little bit of math, but it turns out this whole sum is actually less than multiplied by a special series.

What kind of series?

This series.

One plus a half plus a fourth plus an eighth and so on.

Oh, I vaguely remember that from math class.

It's a classic.

And this series, thankfully for us, converges to the nice number 2.

So all those fractions add up to something manageable.

Exactly.

Which means the total number of bit flips over in increments is actually less than 2 times n.

Wow, so it's like a fixed limit, regardless of how many bits key our counter has.

As long as n is the main factor, you got it.

So the total cost for increment operations ends up being o n, and when we divide that by n to get the amortized cost, it becomes...

A 1.

Constant time on average per increment.

Amazing.

Another victory for aggregate analysis,

giving us a much clearer understanding of the average work involved.

Now let's shift gears to the accounting method.

This one sounds a bit more, I don't know, financial.

It does, right.

It's like we're assigning prices to different operations.

Exactly.

So instead of just looking at the actual cost, we're giving them different amortized costs, which could be higher or lower than the real deal.

Exactly.

And the key here is this concept of credit.

Credit.

Like we're opening a bank account for our data structure.

In a way.

When we assign an amortized cost that's higher than the actual cost, that extra amount is stored as credit.

Like we're overpaying a bit to have some savings later on.

Exactly.

And this credit can then be used later to help pay for operations where the amortized cost is actually lower than the real cost.

So it's like we're balancing the books, making sure we're never in debt.

Precisely.

And there's one crucial rule to make this whole system work.

The total credit we have stored up must always be non -negative.

We can't go bankrupt.

Makes sense.

So we're always able to cover those costs with our prepaid credit.

Now let's revisit our trusty stack example and see how this accounting method plays out.

What kind of amortized costs are we assigning to PoochH, POP,

and MultiPuppy now?

All right.

Let's set things up.

For this analysis, we'll assign an amortized cost of $2 to a PoochH operation.

$2 to push.

Okay.

What about PoochH and MultiPuppy?

For both of those, we'll set an amortized cost of $0.

$0.

But those operations do take some time, right?

How does that work with the credit idea?

Okay.

So when we do a PoochH and we charge those $2, $1 is actually used to do the work of pushing the item onto the stack.

Okay.

That's the actual cost covered.

What about the other dollar?

That extra dollar is stored as credit and it's specifically associated with the item that was just pushed.

Ah.

So each item comes with its own little savings account.

Exactly.

And that's where the magic happens.

Now when we do a POP operation, the actual cost is $1 to remove the item.

Right.

But remember, the amortized cost is $0.

So that $1 actual cost is completely covered by the $1 of credit that was sitting on the item.

So the item pays for itself to be removed.

Exactly.

And the same principle applies to Multipop.

It's essentially a series of POP operations and each individual POP is paid for by the credit of the item being removed.

I love this.

It's like each item brings its own fare for the ride.

Yeah.

And since every item gets this credit when it's pushed and we can't pop something that wasn't pushed in the first place, we're guaranteed to always have enough credit to cover all the POPs.

We're always in the black.

Always.

So even if we do a mix of Impigio H operations costing $2 each in amortized terms and POP or Multipop operations costing $0 each, the total amortized cost stays at O.

Because we're dealing with constant amortized costs for each operation.

Precisely.

And the best part is that because our credit system ensures we never go negative, this O and amortized cost is guaranteed to be an upper bound on the actual total cost.

So it's a reliable way to understand the worst case cost, even when things seem unpredictable.

Now how about that binary counterexample, but this time using the accounting method?

Okay, so for this one, we say that the amortized cost to change a 0 -bit to a 1 -bit during an increment is $2.

$2 to flip a 0 to a 1.

Where does the money go?

Well, $1 is used to pay for the actual flip, the real cost.

Okay, that makes sense.

What about the other dollar?

That other dollar is stored as credit on that newly set 1 -bit.

So it's like the 1 -bits are saving up for something.

Exactly, and here's why.

When a later increment operation needs to flip a 1 back to a 0 because of a carry,

the $1 credit on that 1 -bit is used to pay for that flip back to 0.

Oh, that's clever.

They're prepaying for their eventual reset.

Precisely.

Now, let's think about what happens during any increment operation.

It might flip a bunch of trailing ones back to zeros, and then it changes at most 1 -0 to a 1.

Right, because you might have some carries happening.

Exactly.

For each one that's flipped back to a 0, that cost is already covered by its stored credit.

And for that single 0 that gets set to a 1, we charge $2.

One for the flip, one for future credit.

So no matter what happens during an increment, the amortized cost is capped at $2.

At most $2.

And you know the best part.

Because every 1 -bit in the counter has a dollar of credit on it, the total credit always stays non -negative.

We're never in debt.

So once again, for an increment operation, the total amortized cost is O, which gives us an upper bound on the actual work done by the counter.

You got it.

Okay, so we've covered aggregate and accounting.

Let's tackle our final method,

the potential method.

This one sounds a bit more, I don't know, mysterious.

A bit more abstract, for sure.

Yeah, like we're assigning some sort of energy to the data structure itself.

That's actually a great way to think about it.

In the potential method, we view that prepaid work as potential energy, or just potential of the whole data structure.

The whole thing, not individual parts.

Exactly.

And we have this thing called a potential function, usually denoted as AD, where D represents the current state of the data structure.

It gives us a number, a potential value.

Okay, but how does this potential number connect to the cost of our operations?

Okay, so here's how it works.

The amortized cost of the I operation, we'll call that Ichi, with a little hat on the C, is defined as its actual cost, C, plus the change in potential caused by that operation.

So if an operation makes its potential go up,

its amortized cost is higher than its actual cost.

You got it.

And if it makes the potential go down, the amortized cost is lower.

Like a trade -off between actual cost and potential change.

Exactly.

Now, when you add up the amortized cost of all E's operations, what you get is the total actual cost plus the overall change in potential from start to finish.

Mathematically, that looks like this.

ECT key plus ECE0, where D0 is the final state, and D0 is the initial state of the data structure.

Okay, so we're accounting for how the potential has evolved over the entire sequence.

Exactly.

But to ensure that our amortized costs give us a valid upper bound on the real work done, we usually want the final potential, EZAM, to be greater than or equal to the initial potential, E0.

And a common way to do this is to set EZAO to 0 and make sure ECA never goes negative.

So the potential starts at 0 and never dips below that.

Exactly.

That helps us guarantee that the amortized costs are always an upper limit on the actual costs.

Now, let's go back to our stack example and try to apply the potential method.

What would be a good potential function for a stack, you think?

Hmm.

Well, thinking back to how we analyzed the stack earlier,

maybe something related to the number of items it holds.

That's a great intuition.

In fact, a very natural potential function for a stack is simply the number of items in it.

So S is simply the size of the stack, S.

Nice and simple.

Right.

And the initial potential of an empty stack, S D0, would naturally be 0.

Now, let's think about a PUA shea operation.

It has an actual cost of 1 and it increases the stack size by 1.

So the change in potential is plus 1.

Exactly.

So the amortized cost of a PUA shea becomes 1 plus 1, which is 2.

Interesting.

That lines up with the accounting method where we effectively paid $2 for a push.

It all ties together.

Now, how about that multipop operation?

Let's say it removes K items, where K is the minimum of the stack size in K, that input value.

So the actual cost is K.

Right.

What happens to the potential?

When multipop removes those K items, the potential of the stack decreases by K.

Makes sense.

So the amortized cost would be K plus negative K, which is 0, consistent with what we saw before.

And a simple POP operation with an actual cost of 1 decreases the stack size by 1.

So its amortized cost is 1 plus negative 1, which is 0 again.

Exactly.

And because the stack size can't ever be negative, our potential function is always non -negative.

This means the total amortized cost, which will be O -N for any operation, since each has a constant amortized cost,

is guaranteed to be at least as big as the total actual cost.

Beautiful.

So we've got another solid analysis under our belt.

Now, what about the binary counter example using this potential method?

What kind of potential function could we use here?

All right.

Let's think back to our aggregate analysis for a moment.

Back to those bit flips and how their frequency changed.

Exactly.

Based on that, what do you think might be a useful potential function?

Well, it seems like the number of 1 bits in the counter played a big role.

You're spot on.

We'll define our potential function, Erie, as the number of 1 bits in the counter, A.

OK, sounds good.

So at the beginning, when the counter is all 0s, E0 would be 0.

Perfect.

Now, let's say in the i -th increment operation, tie bits are reset from 1 to 0.

The actual cost, te, is then at most tie plus 1, because you have tie resets and possibly one setting from 0 to 1.

OK, I follow that.

What about the change in potential?

Let's say buy 1 and buy are the number of 1 bits before and after the operation.

We know that buy will be less than or equal to buy 1 minus tie plus 1.

Right, because we're losing tie 1 bits but potentially gaining 1.

Exactly.

OK, so the change in potential, die 1, which is buy minus buy 1, is going to be less than or equal to 1 minus tie.

OK, I see that.

So the amortized cost each would be t plus the change in potential.

Which means it's less than or equal to tie plus 1 plus 1 minus t.

That simplifies to just 2.

Wow, so the amortized cost of each increment operation is at most 2.

And that's O1, a constant.

And like before, since the number of 1 bits can't be negative, our potential function stays non -negative.

This ensures that the total amortized cost for a MAB operation, which is ON, is always an upper bound on the actual cost.

Amazing.

We've tackled stacks and binary counters with all three methods.

Let's move on to something even more practical.

Dynamic tables.

This is something that happens all the time in programming when we use lists or arrays that need to grow or shrink as we add or remove data.

Oh yeah, dynamic tables are everywhere under the hood.

And it's all about managing their size efficiently.

We don't want tons of empty space, but we also don't want adding new items to suddenly become a nightmare when the table is full.

It's all about finding the right balance.

A good load factor, which is the ratio of items to the table size, and low amortized costs for things like inserting or deleting elements.

And our research really emphasizes getting those low amortized costs.

Let's focus first on table expansion.

What happens when we try to insert something into a table that's already completely full?

What's the typical strategy?

A very common approach is to simply double the size of the table when it gets full.

So create a new, bigger table, and then copy everything over from the old one.

Exactly.

And only then can you insert that new item.

But this process has a cost.

If the old table had n items, copying them over takes o n time.

Right, because you have to move each item individually.

And then adding the new item is just o 1, so the total cost for that single insertion that triggered the doubling is o n.

Ouch.

That sounds like a huge performance hit for just adding one item.

How does amortized analysis make this less scary?

Let's start with aggregate analysis for table expansion.

Okay, so with aggregate analysis, we look at a sequence of end insertions into a table that starts empty.

The big picture again.

Yep.

Now, those extensive doubling operations only happen when the number of items is one more than a power of two.

So after one insertion, then after two, then after four, then after eight, and so on.

Right, because that's when we exceed the current table's capacity.

Exactly.

Now, the cost of the i -th insertion is if i minus one is a power of two, because we have to copy all those existing elements.

But it's only one if we're not triggering a doubling.

Okay, so the cost depends on whether we're at that power of two threshold.

Right.

And if you sum up all these costs for n insertions, the total cost ends up being bounded by 3 n.

3 n.

Not bad, considering those doubling operations.

Right.

So the amortized cost per insertion becomes 0 3 n divided by n, which simplifies to just 0 1.

So even though those doubling events are costly, their impact gets spread out over all those cheaper insertions, giving us a constant average cost in the long run.

Exactly.

That's reassuring.

What about the accounting method for table expansion?

How do we figure out the charges here?

Alright, so with the accounting method, we assign each table insert operation an amortized cost of $3.

$3 to insert.

Okay.

$1 is used to pay for the immediate insertion of the new item.

That's the actual cost covered.

What about the other $2?

Well, $1 is stored as credit specifically on that new item.

This credit will be used to help pay for its eventual move when the table needs to expand again in the future.

Ah, so each item is setting aside money for its future relocation.

Exactly.

And the last dollar is also stored as credit.

But this time it's associated with one of the existing items in the table.

It's contributing to the cost of moving all the old items when we expand.

I see.

So everyone is chipping in.

Exactly.

And this ensures that when the table doubles in size, each item in the new, larger table has $1 of credit attached to it.

And that's exactly enough to cover its relocation cost when we need to double again.

It's like a perfectly planned moving budget.

Precisely.

So we always have enough credit ready to go, and the amortized cost per insertion stays constant at $3, or a $1.

I love how this method makes those expansions so much less daunting.

Now what about the potential method for dynamic table expansion?

What kind of potential function do we use here?

This one's a bit more complex, but stick with me.

A useful potential function for table expansion is a day t equals 2 times t dot num minus t dot size.

Okay, so t dot num is the number of items currently in the table, and t dot size is the total capacity of the table.

You got it.

Now notice what happens right after an expansion.

The size of the table is exactly double the number of items, so t dot num equals t dot size divided by 2.

Right, because we just doubled it.

Exactly.

And if you plug those values into our potential function, it all simplifies to zero.

So right after an expansion, the potential is zero.

Interesting.

But then, as you keep adding items, the potential starts to increase.

When the table becomes completely full, so t dot num equals t dot size,

the potential becomes equal to t dot size.

So the potential grows as the table fills up.

And that growth in potential is essentially storing up enough to cover the cost of the next doubling operation, which remember is o t dot size.

Oh, I see.

It's like we're building up a reserve fund.

Precisely.

Now, if you carefully analyze the amortized cost of an insertion using this potential function, you can show that it's at most three.

So we get that same o one amortized cost that we saw with the other methods.

Exactly.

The potential method confirms that even with these expansions, the average cost per insertion remains constant.

That's fantastic.

All three methods show us that dynamic table expansion is actually quite efficient on average.

But what happens when we want to make the table smaller because we've deleted a bunch of items?

That's an important point.

You might think, okay, let's just halve the table size whenever the load factor goes below half.

Seems logical, right?

Keep things compact.

It does.

But here's the catch.

Imagine a scenario where you're adding and removing items in a way that keeps the load factor hovering right around that half mark.

Okay.

So we're constantly teetering on the edge of needing to resize.

Exactly.

And what could happen is that the table repeatedly doubles and then halves its size over and over again.

And each of those operations is costly.

It takes o n time to copy everything.

Oh, no.

We'd be wasting so much time resizing back and forth.

Precisely.

So that simple rule of having it half capacity can lead to a very inefficient situation.

So what's a smarter way to manage both growing and shrinking the table?

Well, a more effective strategy is to use different thresholds for when we trigger expansion and contraction.

Typically, we still double the table size when an intrusion would make it full.

So when the load factor reaches one.

Okay, that part stays the same.

But we only have the table size when a deletion causes the load factor to drop significantly lower, usually below one fourth.

And importantly, after a contraction, we ensure that the load factor is at least one half.

So we're not immediately shrinking back down to a very low load factor.

Exactly.

This gap between those expansion and contraction thresholds, one and one fourth, prevents that rapid back and forth resizing that we were worried about.

It gives us some breathing room.

Precisely.

Now, the next step is to define a potential function that handles both of these rules.

A potential function that can deal with both expansion and contraction.

And the chapter provides a really clever one.

It's a two -part function.

At equals two times t dot num minus t dot size divided by two, when t dot num is greater than or equal to t dot size divided by two.

And the other part is At equals t dot size divided by two minus t dot num, when t dot num is less than t dot size divided by two.

Okay.

So the potential function depends on whether the number of items is above or below half the table's capacity.

Exactly.

And with this function, the potential is zero when the load factor is exactly one half.

When the load factor gets closer to one, meaning we're approaching full capacity, the first part of the function takes over and the potential increases.

So we're storing up potential as we get closer to needing expansion.

Exactly.

And when the load factor drops closer to one fourth, meaning we're getting sparse, the second part of the function takes over and the potential increases again.

So we're also storing up potential as we get closer to needing contraction.

Precisely.

And if you go through the analysis using this potential function, you can show that both table insert and table delete operations have an amortized cost of O1.

So even with both expansion and contraction, we're still maintaining that constant average cost per operation.

Exactly.

It's incredible how these techniques allow us to design dynamic data structures that adapt to changing data while remaining efficient.

Amortized analysis is truly powerful.

It allows us to understand the real long -term performance implications of these data structures.

Absolutely.

And it takes us beyond just worrying about that one rare expensive operation in the worst case scenario.

It gives us a much more realistic picture of how things behave over time.

So as we wrap up, we've seen how amortized analysis helps us understand that average per operation in a sequence,

even when some individual operations might be quite expensive.

We explored three key methods,

aggregate analysis, the accounting method, and the potential method.

And each method gave us a different but ultimately consistent view of the amortized cost.

Exactly.

We saw how these methods apply to stacks, even with that tricky multi -pop operation, revealing that its amortized cost is constant, even though a single multi -pop could take linear time.

We also saw the constant amortized cost for incrementing a binary counter, even though a single increment can flip multiple bits.

And finally, we tackled dynamic tables, demonstrating how intelligent resizing strategies analyzed through amortized analysis result in those amazing constant average costs for both adding and removing elements.

It's amazing how often amortized analysis reveals an efficient average cost, where just looking at the worst case scenario might lead us to a much more pessimistic conclusion.

Absolutely.

And understanding these concepts is crucial for designing efficient and scalable software.

It really highlights the power of thinking about the prepaid work or the potential within a data structure to handle those less frequent but more expensive operations.

Well, this has been a fascinating journey into the world of amortized analysis.

It makes you think differently about those operations in our technology that might seem costly at first glance.

Maybe when we consider them as part of a sequence, their average cost is much lower than we think.

It's almost like this idea of potential or prepaid work is happening all around us in ways we don't even realize it's a really thought -provoking concept.

Thanks for joining me on this deep dive.

It was my pleasure.

Until next time.

Indeed.