Amortized Analysis | Data Structures - YouTube

Hey guys, in this video I'm going to do a question in Data Structures about amortized

analysis. This one says, determine the amortized cost of adding to an array-backed heap.

So we're just looking at the add() method.

And it says assume the following resize

strategy: that the initial capacity is equal to 1, and when the array is full, you double the capacity

when you resize it to add again. For these types of amortized cost questions,

you're going to know basically what the runtime is of each operation, and you can do it for several times.

So you can go from 1 to N.

And then you should be able to see--it's basically, the definition is that when you have a sequence of operations

and you know the pattern of their runtimes, you can do an amortized cost analysis for that

method. I'm going to go ahead and get started.

So we're going to do a little table that shows the runtime cost of each operation.

We're going to find the amortized cost of the total N operations

and then we're going to find the amortized cost per operation.

Like I said,

we're going to go from adding one, two, and then just enough times until we can find a pattern.

I'm going to go up to nine.

And we are given enough information to know what

to do with the capacity, the resize, and the cost.

The first time you're adding to the array, the array is empty, and it has a capacity of one.

You don't have to resize because all we're doing is adding for the first time and

we're just going to say that we know, or you should know

when you're doing this, what the cost of adding to an array heap is. So that's going to be--in general

it's O(log N).

When you're adding one, the

cost is going to be log(1), and so we're done with the first one. Now to add

a second time to the array, we have to resize. So we have to do our first resize.

The capacity is now going to be two because we know from the

strategies that we double the capacity

when the array is full. And so the cost is going to be the cost of adding--our N

is two here--so it's log(2) plus the resize cost is one. So we have log(2) + 1

for adding a second item. Our capacity is two. To add a third item to the heap,

we're going to have to resize again.

Now our capacity is four and the cost is going to be log(3)

plus the cost of adding two.

We don't have to resize to add four, so our capacity is still four.

We leave this blank, and it's going to just be log(4) for the cost. For five,

we're going to have to resize again because our capacity was four.

We resize and add four, so our

capacity is now eight. And the cost of adding five is going to be log(5)

plus the resize cost, which is four. And now we're going to be able to add up to eight without having to resize.

Our capacity can stay at 8. We don't have to

resize. This is going to be log(6). This is going to be log(7). Eight is still going to be just

log(8)

and then we're going to do one more final resize. To double, we're going to add eight.

Our capacity is going to be 16 and then the cost is going to be log(9) + 8.

Okay, so this is enough of the table filled out to notice a distinct pattern with the cost column. We see that if

you consider this to be N, the cost is log(N)

plus the cost of resizing. At the bottom, let's go ahead and figure out what the patterns are.

For N total operations,

you see that the cost is log(N), and we're doing this N times

plus the cost of resizing. The resizing--the pattern is

essentially 1 + 2 + 4 + 8 and it's that sequence of numbers. So 1 + 2

+ 4 + 8, which is essentially doubling each time. And the formula for that is going to be 2n - 1.

So when N is 1, you have 2 - 1 that's 1, and so on. The pattern

overall is N * log(N) + 2N - 1. When it's asking for the total or overall

amortized cost, you want to give that in a big O notation.

If you take the big O notation of this, it's going to be O(nlog(n)).

Because O(nlogn) is bigger than O(n), and you have an addition here. This would be basically

O(nlogn) + O(n). The final answer for the total amortized cost is

O(nlogn). And the cost per operation, you just divide that by N, and you would get

O(log N)

per call to the add method, and that's pretty much it. So we are done with this problem.

*chiptune music plays*