Transcript


00:16
okay let's see I have a request from a
00:23
student to change the date of the first
00:27
exam it's scheduled for next Friday
00:31
which is the 30th and I guess the
00:35
rationale is that there's a job fair on
00:37
Monday and Wednesday which takes time to
00:39
get ready for and so they'd rather have
00:42
the exam moved from next Friday to the
00:44
following Monday you know I guess it
00:49
doesn't make any difference to me
00:50
whether the exam is Friday or Monday but
00:52
it may make a difference to others who
00:55
have planned on having the exam on
00:57
Friday and probably have other things
01:00
set up for October one and two and three
01:05
so if anybody has other plans for that
01:13
weekend and would rather see the exam
01:14
stay on Friday well let me see if
01:17
there's any from amongst you who would
01:19
rather just have the exam done on Friday
01:22
you would okay so we'll stay with
01:25
fried-egg this test today we were
01:26
planning to do it okay all right so no
01:29
change in the exam date next Friday now
01:32
there are sample exams posted on the
01:35
website and you certainly want to try
01:39
those out after you have prepared for
01:40
the exam give you a good idea of the
01:45
kinds of questions that are asked also
01:47
the amount of time you get to do the
01:50
questions basically what you'll see is
01:53
the questions are of the type well
01:56
here's the data structure how would you
01:58
perform a particular operation on it
02:01
okay and you really need to have the
02:09
data structures at the top of your mind
02:11
when you come for the exam you'll have
02:13
plenty of time to do the operation like
02:15
if I give you a an interval heap and say
02:19
insert this item it doesn't take a whole
02:21
lot of time for you to redraw the tree
02:23
after you've done the insert provided
02:25
you know how to do the insert
02:27
the exam will have plenty of time to
02:30
draw the tree but you're not going to
02:31
have time to try and reinvent the insert
02:33
out with them so you have to know how
02:35
insert works so that you can do it okay
02:38
so be sure you know how how the
02:41
different operations work and if you do
02:43
you should be able to finish the exam
02:46
and a lot less time than is allocated
02:48
for the exam okay you have any questions
02:52
you want to ask yeah yeah yeah yeah yeah
03:06
well I guess what one way is to just try
03:08
and base it on the way we do it for
03:10
interval heaps okay because it's the
03:12
same kind of idea in an interval heap
03:14
you have this total correspondence and
03:16
you have essentially total
03:17
correspondence and a deep also so you
03:19
could model it based on how into heaps
03:21
work or you could model it based on how
03:25
it works for ordinary heaps where you
03:27
start at the bottom at the rightmost
03:29
part of the array and move you know
03:31
towards the left where so what you're
03:35
sitting at a node you make sure that
03:37
both its left and right subtrees are
03:40
deeps by the time you come to examine
03:42
the root of that subtree and then you
03:47
ensure that you have a deep after you're
03:49
done with that node okay
03:51
so I think either of the two strategies
03:54
will work if you have a problem stop by
03:57
in my office and we try and go through
03:59
one or both of the strategies okay all
04:03
right other questions
04:08
alright last time we started to talk
04:11
about a binomial heap we saw how the
04:14
different operations supported by a
04:17
binomial heap work we also saw the worst
04:20
case complexity of individual operations
04:22
and today what we want to do is really
04:26
just go and establish the amortized
04:29
complexity so today's lectures just
04:33
going to be an analysis lecture will see
04:36
that the mathematics involved in the
04:37
analysis is not very deep at all it's
04:40
probably like 5th grade math but there's
04:42
a lot of reasoning that goes behind it
04:44
and it's basically using the potential
04:47
method or the accounting method to
04:50
arrive at the analysis the aggregate
04:53
method as we'll see has no hope of
04:55
getting us the right or the results
04:57
we're trying to get on this particular
04:59
problem alright first let's take a quick
05:02
review of what we did in the last
05:03
lecture okay so the operations being
05:08
supported insert remove and meld the
05:13
actual complexity we saw last time for
05:15
an insert is order 1 it's order n for a
05:19
remove men and order 1 for a melt and
05:21
today what we wanted to do is we want to
05:23
show that even though the actual
05:25
complexity is bad because one of the
05:27
operations takes linear time the
05:29
amortized complexity is actually fairly
05:31
respectable its order 1 for the insert
05:34
and the melt and login for the remove
05:36
mint the insert operation but this
05:45
basically worked by creating a new min
05:48
tree single node venturi and putting it
05:52
into your collection of min trees a meld
05:58
was just combining two circular listen
06:01
to one so both of these operations ran
06:03
in order one time and then the remove
06:07
men is one where in addition to taking
06:12
out the element with the smallest
06:14
priority we did some extra work and that
06:17
extra work was pairwise combining of
06:19
trees that had the same degree
06:23
we saw last time that the complexity of
06:27
the remove Minh topper Asian was order
06:29
of the max degree plus s where s is the
06:32
number of min trees you have just prior
06:35
to the pairwise combining right we also
06:46
introduced the notion of a binomial tree
06:49
and this is by definition that's what a
06:52
binomial tree is the definition isn't
06:57
something that comes because somebody is
06:59
talking about binomial heaps it's really
07:01
you have the definition first and then
07:03
you show that the trees binomial heaps
07:05
create our binomial trees okay all right
07:08
so by definition a binomial tree BK is a
07:15
tree that has degree K so the root has K
07:20
children okay
07:22
it's B K for K bigger than 0 is made up
07:27
of to be K minus ones that was the
07:30
alternative definition we saw last time
07:32
b0 itself is simply a single node tree
07:42
we saw a few examples so b0 is a single
07:45
node tree b1 is made up of to be zeros
07:49
b2 is made up of two b1 and b3 is made
07:52
up of to be twos okay and that's a
07:55
matter of definition and from this it
08:00
was easy to see that the number of nodes
08:01
in B K is 2 raised to K alternatively
08:09
the degree is logarithmic in the number
08:12
of nodes so K is log of the number of
08:19
nodes in the tree
08:24
right towards the end I said that all
08:28
trees that are created in by normal
08:31
heaps they're all binomial trees and you
08:37
can prove that by induction we know that
08:41
insert creates only be zeros ml doesn't
08:47
create new trees the only other place
08:52
new trees are created is when you do
08:53
pairwise combines and pairwise combines
08:57
take two trees of equal degree make one
08:59
a subtree of the other okay and so from
09:04
these three it follows that the only
09:06
trees you can get a binomial trees
09:10
there's no way for any other kind of
09:13
tree to show up in the system if you
09:20
perform a total of n operations then the
09:26
worst they can happen to you is that all
09:27
of them are inserts and as a result you
09:35
cannot create a binomial tree that has
09:37
more than n elements so if you look at
09:45
any sequence of n operations and you
09:49
look at the binomial trees following
09:51
okay the performing of those operations
09:55
no binomial tree can have more than n
09:57
elements in there because you couldn't
09:59
have introduced more than n in the whole
10:00
system as a result and so no binomial
10:05
tree can have a degree that's more than
10:08
log n okay so if you perform an
10:13
operations the max degree is bounded by
10:15
log N
10:22
so the actual complexity would remove
10:25
men which was max degree plus s Israeli
10:28
order of log n plus s and since s can be
10:33
of the order of n your whole complexity
10:36
can be order of n so even though max
10:43
degree is bounded by log n the S can be
10:46
as big as n so your overall complexity
10:48
is order of n actual complexity alright
10:55
so all of that is kind of review of what
10:58
we did last time let's try and establish
11:04
the amortized complexity and we saw that
11:09
there are really three common ways to do
11:12
this one is the aggregate method then
11:14
the accounting and the potential so
11:17
let's try all three of these and see
11:18
which work so a first attempt may be to
11:21
try to aggregate method intuitively
11:23
that's the easiest one to work with
11:26
though or the with some of the examples
11:29
we saw the mathematics gets harder with
11:31
the aggregate method than it is with the
11:32
others the strategy here is to obtain a
11:38
good bound on a sequence okay so you say
11:40
got a sequence of n operations doesn't
11:42
matter what the sequences find a good
11:44
bound on the total complexity of that
11:46
sequence and then you divide by n and he
11:50
say well that's the amortized complexity
11:51
of an operation in the sequence you know
11:58
problem with this strategy is that
12:00
you're going to get the same amortized
12:02
complexity for an insert as you will for
12:04
a remove min and a melt and that's not
12:07
what we're trying to show we're trying
12:09
to show different amortized complexity
12:11
for a remove 'men than for an insert or
12:15
remote
12:20
so certainly this strategy that we'd use
12:23
in the past consider an arbitrary
12:26
sequence of size n figure out its total
12:28
cost divided by n has no hope of working
12:33
so we might try to modify this and say
12:36
well I want a different bound for remove
12:39
montañas so why don't just look at
12:44
sequences of remove Minh tear costs and
12:48
divide by the number of movements in the
12:50
sequence I could do the same thing for
12:52
inserts and for mell separately well
13:01
when you try to do this if you look at
13:03
the following sequence here where you do
13:05
a large number of inserts so you do n
13:09
minus 1 inserts and then you do a remove
13:10
in okay well the complexity of that
13:15
remove men is going to be n order event
13:19
and there's only one remove Minh in the
13:21
sequence so you end up with an amortized
13:26
complexity of n so even a modified
13:34
version of the aggregate method has no
13:37
hope of getting us the bound that we're
13:40
trying to establish and this is pretty
13:47
much the case for most amortized
13:49
analysis and data structures because the
13:51
bounds we're trying to establish a
13:53
different for the different operations
13:54
done on the data structure the aggregate
13:57
method is really of no use all right so
14:06
let's go to the accounting method
14:14
well the strategy here is to guess the
14:16
amortized cost of an operation and so
14:20
you're free to guess any cost you like
14:22
you don't have to guess the same cost
14:24
when insert as for a movement or a melt
14:27
so now you can guess different costs
14:29
okay so the method adapts itself to
14:32
cases where costs are different for
14:34
different operations of course you have
14:36
to do guessing in all our previous
14:40
examples the guessing was easy because
14:41
the aggregate method worked there was
14:43
kind of a direct way to get the
14:44
complexities and we already knew the
14:46
answer okay now we don't know the answer
14:49
so we have to guess and this is where
14:52
having a good crystal ball becomes
14:54
effective
14:55
so you guess something you try to prove
14:57
it it doesn't work you go back and guess
14:59
again okay all right so here we're going
15:03
to guess something that works is we're
15:04
going to iterate through this thing
15:05
several times so I'm going to guess that
15:07
the amortized cost of an insert is two
15:10
and that the amortized cost over meld is
15:13
one and that the amortized cost over
15:16
remove men is three log of n base two
15:26
now there's no point asking me where did
15:29
these guesses come from and it's a guess
15:33
so it's a guess you guess you get
15:35
something you go through the balance of
15:38
what has to be done with the method and
15:40
see that the balance of it works out and
15:42
if it doesn't you go back and guess
15:44
again certainly as you do more and more
15:48
amortized analyses and as you feel more
15:51
comfortable with the data structure
15:52
you're trying to analyze you get better
15:55
at making guesses that work all right so
15:59
I'm going to guess this stuff and
16:01
hopefully I'm going to be able to show
16:03
that with this guess the potential is
16:05
non-negative because that's the strategy
16:07
you guess the amortized cost and then
16:10
you need to show that the potential is
16:11
non-negative and if you can show this
16:14
then you know that you had a good guess
16:16
if you can't show it you don't have a
16:18
good guess okay all right
16:23
so you show the potential nonnegative
16:25
let us refresh ourselves as to what
16:27
potential is so potential is really
16:31
something which keeps track of the
16:32
amount of overcharged amortize constants
16:35
what you're charging actual cost is what
16:37
is really costing you so if we take the
16:40
difference between these two that's the
16:41
amount of the overcharged if it's
16:43
negative it was an undercharge if it's
16:45
positive it isn't overcharged okay so
16:47
the potential keeps track of the amount
16:49
by which you have overcharged the first
16:51
I operations so potential after the
16:57
eyuth is the amount by which you
17:00
overcharge the i/o operation plus the
17:02
accumulated overcharge from the previous
17:04
operations so PR minus p0 is the amount
17:13
by which you have overcharged the first
17:15
I operations and we need to show that P
17:22
I minus p0 is non negative a common way
17:31
to show this is to use the credit scheme
17:36
so in the credit scheme we try to keep
17:38
track of the total amount of overcharged
17:41
so far by placing this overcharge at
17:44
interesting entities in the structure
17:46
and that makes it easy for you to show
17:49
that your potential is non negative at
17:52
all times so the strategy we're going to
17:57
use here is the credits okay the amount
18:00
of what we charge are going to be placed
18:03
on the trees and they're going to be
18:06
placed let's say on the root of the tree
18:07
we'll make sure that every tree has one
18:10
unit of credit associated with it if the
18:16
amount of overcharge exceeds the number
18:18
of trees you have we'll just throw away
18:20
the excess overcharge it won't be of any
18:23
use in our proof so
18:28
like the binary counter in the binary
18:31
counter if you recall we kept the credit
18:33
on everyone and I was used to pay for
18:35
the time you change the one to zero okay
18:38
so here we'll keep a credit on every
18:40
tree and that credit will be used at the
18:43
time you do a pairwise and combine okay
18:48
all right when we start the number of
18:57
credits will be zero so p 0 0 as a
19:01
result P I is the amount of overcharge
19:04
after the I thought relation alright so
19:13
let's go through the operations ok we do
19:17
an insert so when you do an insert you
19:19
add a tree to your collection of trees
19:21
okay when you add a tree if we are going
19:25
to follow our discipline of credits we
19:27
need to be able to leave one credit on
19:29
the tree ok so that will ensure that all
19:32
the trees have one credit ok so when you
19:36
start the insert all the trees have
19:37
credits you create a new tree we'll put
19:39
one credit on it the result is that
19:41
every tree has a credit the amortized
19:46
cost we guessed is to the actual cost is
19:49
1 we'll use that one unit of actual cost
19:53
we'll use one of the two units of
19:56
amortized cost to pay for the actual
19:58
cost of the operation so now we're left
20:00
with one so that's an over charge of one
20:02
and that's good because that's what I'll
20:05
use to put the credit on the tree
20:14
okay so with this scheme I ensure that
20:19
every tree at least every newly created
20:23
tree has a credit on it
20:39
well the potential is going to be the
20:41
number of credits okay
20:45
so when you do an insert the potential
20:48
goes up by one you charge the operation
20:51
one unit more than it constitute or when
20:57
you do a meld there's no change in the
21:02
number of trees so there's really no
21:05
change in the potential and so we don't
21:10
need to charge the milled any more than
21:13
its actual cost right so the guessed
21:18
cost is one the actual cost of a meld is
21:22
one I use the guessed amortized cost to
21:26
pay for the actual cost that leaves me
21:28
with no surplus which is fortunate
21:30
because I don't create any new trees and
21:31
which I have to leave a credit
21:49
look at the remove man operation
22:00
all right to figure out the actual cost
22:02
of this operation will introduce some
22:05
variables okay so you have a collection
22:10
of men trees so in this particular case
22:16
if you did a remove men from this
22:18
binomial heap then where I've got one
22:20
two three four five six men trees okay
22:24
so men trees refers to this collection
22:26
of men trees and there are six of them
22:29
okay and then if you do a remove when
22:31
and if the room minimum element was the
22:33
root of this green tree you take that
22:35
fellow out so the number of trees goes
22:38
down from six to five but then you put
22:40
these two guys back so you go up to
22:42
seven that's the S value just before you
22:47
start the pairwise combined you'll have
22:49
seven trees on what you're going to do
22:50
the pairwise combined okay agree with
22:56
that okay all right so mint trees refers
23:02
to the whole set the size of men trees
23:04
is six okay so let you be the degree of
23:08
the men tree whose root is removed in
23:10
the example I just went through you is
23:12
to I removed the root of that green tree
23:17
so you is to s is the number of entries
23:23
that binomial heap just before the
23:24
pairwise combined so in this particular
23:26
case s will be seven
23:33
okay s is the number of men trees plus
23:38
the degree of the tree that had the
23:42
smallest value minus one so you start
23:47
with this many trees you take out the
23:49
one with the minimum okay and then you
23:52
put blankets children right so s is
23:57
number of men trees plus u minus one any
24:01
questions about that the actual cost
24:11
ever removed men okay is max degree plus
24:18
s so max degree is at most log N and s
24:37
is this fellow here but you also can be
24:41
at most log n because U is also a
24:44
binomial tree is the the tree we took
24:48
out the green fellow was a binomial tree
24:51
and so the degree of the green fellow
24:55
was at most log n ok so this is a number
25:04
of trees you started with that's at most
25:06
log n this is at most log n so that's 2
25:09
log n minus 1 sorry max degree is log n
25:17
U is log N and then this thing stays
25:20
right so you get 2 log n minus 1 plus
25:23
min trees number of men trees all right
25:29
any questions about that everybody
25:31
agrees with that bound down that yeah
25:37
yeah so what I'm doing is I'm adding
25:41
these two things together max degree and
25:43
s okay so max degrees at most log n okay
25:47
and then I got the S term so s is min
25:51
trees plus log n minus 1 so I got a log
25:57
n from here another log n from there so
25:59
that's 2 log n minus 1 plus this term
26:01
there okay all right okay all right so
26:09
the actual cost is at most 2 log n minus
26:11
1 plus number of min trees the guessed
26:20
amortized cost is 3 log n the actual
26:26
cost is this sometimes this would be
26:35
more than that and sometimes this will
26:37
be less than that okay so sometimes
26:40
you're overcharging that operation
26:43
sometimes you're under charging it but
26:45
we need to show that with the
26:46
accumulated credits I always have enough
26:49
to pay for the operation you can't pay
26:53
for an operation from future operations
26:55
because future operations may not take
26:57
place ok so you got to pay for every
27:00
operation from past operations and the
27:02
current one all right so I'm going to
27:11
first say how am I allocating this 3 log
27:14
n ok what do I do with the 3 log n some
27:19
of it is going to be used to pay for the
27:21
actual cost some of it is going to be
27:23
used as credits then I'm going to show
27:27
how do I pay for all of this because all
27:30
of this is not going to get paid from
27:32
the 3 log n is going to get paid from
27:34
part of the 3 log N and from part of the
27:37
credits alright
27:43
first let me tell you what I'm going to
27:45
do with the amortized cost I'm going to
27:49
use two log n minus one of the amortized
27:51
cost to pay for part of the actual cost
27:54
so it'll pay for this part of it the
27:56
front part okay so that's going to still
27:59
leave me with log n plus one unused
28:04
charges these are going to be kept as
28:10
credits so the remainder three log n -
28:14
what you using here the log n plus one
28:17
these are going to be kept as credits
28:22
which will be used to pay for future
28:24
remove means not for the present one
28:27
okay and the way we're going to keep
28:30
track with these credits is after you
28:33
are done with the pairwise combined okay
28:36
the number of trees you'll be collecting
28:39
out of that array is going to be at most
28:42
log n plus one because max degree is log
28:44
n so degrees can run from zero through
28:47
log n log n base two so their log n plus
28:50
one such trees that you might create
28:53
okay so I've got enough credits here to
28:59
pay for all of the trees that remove men
29:02
is going to leave behind these could be
29:04
newly created trees they didn't have
29:06
credits on them all right so I guess an
29:14
amortized cost of three log n 2 log n
29:18
minus one is going to be used to pay for
29:20
part of the actual cost okay
29:23
so I've only paid for this much I've yet
29:25
to figure out how I'm going to pay for
29:26
that much after I've used this two log n
29:32
minus one I'm left with log n plus one
29:36
these are going to be used to place the
29:38
credits on the trees that are left
29:40
behind after the remove 'men operation
29:43
and they can be at most log n plus one
29:45
such trees so you can leave one credit
29:50
per tree and that maintains the
29:52
invariant which said that every tree has
29:53
one unit of credit on it
29:58
or any questions about how we're using
30:01
the amortized cost
30:13
and if you have any extra credits you
30:16
can throw them out so for example there
30:23
may not actually be this many trees that
30:25
result following the pairwise combined
30:28
but they can't be more than that okay so
30:31
if you have fewer you got excess credits
30:32
we aren't going to keep track of those
30:34
they're not needed yep
30:43
does discarding the remaining credits
30:45
reduce the amortized cost well whether
30:52
it reduces the amortized cost or not is
30:54
something you will know only if you went
30:55
back and tried to do a proof would say
30:58
2.5 log n say to see if you were still
31:01
prove it with 2.5 log n now since in at
31:07
least in this particular case it doesn't
31:08
really matter whether you show the
31:10
amortized cost it's 3 log in a rate log
31:12
n because in the end we're going to say
31:13
it's order of log n there's no advantage
31:16
to trying to come up with a title proof
31:18
than this one
31:28
all right so now how do we pay for the
31:31
actual cost we've already seen that the
31:38
front part to log n minus one that comes
31:41
from the amortized cost of that
31:42
operation the remainder each of the
31:50
trees that you had before you started
31:52
the remove ment okay so now example we
31:56
had six such trees each one of those had
31:58
a credit on it so I'm going to use up
32:01
all of those credits to pay and the
32:04
number of credits will be exactly equal
32:05
to number of men trees so all the
32:10
credits on those trees get used up to
32:12
pay for the balance of the actual cost
32:14
and that's not a problem because once
32:18
you're done with the operation you get a
32:20
new set of trees and we're putting
32:21
credits on them from the allocation of
32:24
the three log n that we just went
32:25
through okay all right so I've got
32:30
enough to pay for the whole operation
32:32
from credits from previous operations
32:35
plus part of the amortized cost of the
32:38
current operation I've got enough to
32:40
leave a credit on every tree after I'm
32:42
done
33:02
so since you can pay for the whole
33:04
operation your potential remains
33:05
non-negative potential in this case the
33:08
total number of credits the number of
33:10
credits doesn't become negative or any
33:18
questions about the analysis using the
33:21
accounting method you guess and then
33:25
show that you guess then you use I
33:27
scheme to keep track of the total
33:29
overcharge the credits and once you have
33:34
that then you need to be able to show
33:35
that you have enough to pay for every
33:37
operation
34:37
okay any questions
34:49
all right now we'll see how to do the
34:51
same proof you have a question yeah yeah
35:01
right
35:45
okay then
35:54
oh let me repeat what I said with this
36:00
thing okay from the three log n I use to
36:03
log n minus one to pay for that part of
36:05
the actual cost that leaves me with the
36:07
log n plus one credits these log n plus
36:11
one credits are going to get used on the
36:14
trees that are left after you have done
36:16
the pairwise combined okay so we do the
36:19
pairwise combined and once you're done
36:21
with that you're going to be left with
36:23
some number of trees those trees don't
36:25
have any credits on them because as we
36:27
saw whatever credits any of those trees
36:29
had got used up to pay for the Farwest
36:32
combining okay so the trees that are
36:35
left after the pairwise combined will
36:38
get credits placed on them and those
36:40
credits will come from here the number
36:43
of trees that you can be left with after
36:44
the pairwise combined cannot exceed log
36:47
n plus one because max degree is log N
36:49
and so this total amount here is enough
36:53
to leave one credit per tree that you
36:56
have after the pairwise combined okay
37:04
all right there are no other trees on
37:06
which you had to put credits
37:13
all right so let's take a look at
37:18
getting the same results using the
37:22
potential method the strategy here if
37:25
you recall is to guess a potential
37:27
function potential function needs to be
37:29
non-negative
37:30
and then once you have guessed the
37:33
potential function you make use of the
37:36
potential function and actual cost to
37:37
figure out the amortized complexity so
37:41
you guess a suitable potential function
37:43
needs to be non-negative there's this
37:47
once you have the potential function you
37:50
can compute the change in potential as a
37:52
result of doing an operation and there
37:59
is a formula which says the change of
38:01
potential is amortized cost minus actual
38:04
cost ok so we're going to employ this
38:12
relationship between potential change
38:14
and amortize an actual cost to arrive at
38:20
this which says the amortized cost is
38:22
actual cost plus potential change so you
38:26
guess the potential function for each
38:29
operation I'll compute the Delta P and
38:31
add it to its actual cost that will give
38:34
me the amortized cost of that operation
38:40
so like the accounting method there's
38:43
some guesswork here you have to guess a
38:45
suitable potential function in the other
38:47
case we had to guess the amortized cost
38:49
directly here you have to guess the
38:51
potential function ok now once you have
39:00
done the accounting method it's not hard
39:04
to guess a potential function that's
39:05
going to work because the potential
39:07
function keeps gives you the aggregate
39:09
credits and from the accounting method
39:13
we know that the potential we need to
39:16
keep track of is the number of trees so
39:21
I'll
39:22
users my guess the potential function is
39:25
the number of trees that you have and
39:28
I've got a J there because I have to
39:33
have many binomial heaps if I'm going to
39:36
do a melt because if you're doing ml do
39:39
you have to have at least two binomial
39:41
heaps that you're molding together
39:42
okay so J indexes the different binomial
39:45
heaps you have each binomial heap could
39:46
have a different number of binomial
39:49
trees in it okay so when trees J gives
39:53
you the set of min trees in the jeaious
39:56
binomial heap and you add up the number
39:59
across all of the binomial heaps that
40:00
you have that's the potential okay
40:04
all right and you do this after the eye
40:07
operation
40:17
so when you Mel to buy normal heaps the
40:22
input heaps a and B disappear so they
40:25
drop out from this thing but there's a
40:26
new heap created and that pops in to
40:29
this Sun right when you start the
40:35
potential is zero you have no min trees
40:37
in any of your binomial heaps the
40:42
potential is always non-negative because
40:44
you can't have a negative number of min
40:46
trees in any heap so it satisfies the
40:50
minimal requirements it's a non-negative
40:53
function alright so let's go through the
41:02
operations okay so suppose that the
41:04
eyath operation is an insert the actual
41:12
cost is 1 the change in potential
41:15
potential is the total number of trees
41:16
will you do an insert total number of
41:18
trees goes up by 1 okay so Delta P is 1
41:25
okay so the actual cost of an insert is
41:28
1 the potential change is 1 and so the
41:31
amortized cost is actual cost plus
41:34
change in potential and that's 2
41:47
okay Russ suppose that the i/o operation
41:55
is a meld the actual cost is one
42:00
potential change it doesn't change the
42:02
number of trees so there's no change in
42:04
potential the amortized cost is actual
42:10
plus potential change so one plus zero
42:12
it's one so the last case is you're
42:25
looking at a remove mint operation here
42:30
I'm going to need to keep track of the
42:33
number of min trees before and after the
42:34
operation so I'll introduce a
42:37
superscript old which is the value of a
42:39
variable just before the remove Minh and
42:42
new is the value of a variable just
42:45
after the remove Minh so number of mint
42:52
trees old J gives me the number of mint
42:54
trees in the jf heap just before this
42:56
removal in operation and similarly
42:59
number of min trees new would give me
43:00
the number of min trees in that heap
43:02
just after the operation because these
43:06
quantities will change only for the min
43:08
heap in which you do the operation not
43:10
for the others okay so let's suppose
43:14
that the remove Minh takes place from
43:15
the KF binomial heap so then only for J
43:18
equals K do number of min trees old
43:21
differ from number of min trees new for
43:24
the others old and new are the same
43:29
right so the actual cost of a remove
43:31
Minh from the KF binomial heap is we saw
43:36
the formula before 2 log n minus 1 plus
43:39
the number of min trees just before the
43:41
operation
43:46
the change in potential okay this is
43:52
changing potential for the whole system
43:54
is potential after the operation -
43:59
potential before the operation okay so
44:02
before the operation is some of men
44:03
trees sorry after the operation some of
44:05
men trees new before the operation some
44:07
of men tree is old subtract the two and
44:10
as we said this quantity differs from
44:13
that only when J is K okay so this is
44:17
min trees new K - min trees old okay all
44:25
right so actual cost potential change
44:28
we add the two that's the amortized cost
44:37
right so if I add these two min trees
44:40
old cancels out they got a plus and a
44:43
minus so I got 2 log n minus 1 plus min
44:46
trees new
45:00
now after a movement because of the
45:03
combined operation all of them in trees
45:06
you have our different degree and the
45:08
maximum degree is log n so you can have
45:11
one of degree zero one or degree one one
45:14
of degree log n so this quantity here is
45:17
at most log n plus one so it's three
45:25
logger
45:52
all right questions about this analysis
46:06
I said this is a fairly complex analysis
46:10
I certainly don't expect that you're
46:13
going to be able to do something of this
46:14
order in in an exam well took an hour to
46:18
explain it but it's nice to see it to
46:23
get confidence that when an assertion
46:26
was made the complexity in fact was log
46:28
n then there is a proof behind it you
46:31
notice that the the mathematics isn't
46:33
difficult there's no fancy calculus
46:35
anything going on in there it's just a
46:36
lot of logic some guesswork we'll
46:40
probably see one more maybe two more
46:43
amortized analyses in this class there
46:46
will be one where we will start with the
46:47
potential function because it's going to
46:49
be hard to guess and use the accounting
46:52
method so there we're going to guess a
46:54
potential function and do the proof okay
46:57
all right questions yeah
47:08
yeah okay so questions how is this
47:14
quantity here at most log n plus-1 said
47:18
after you do the pairwise combined okay
47:20
the trees that you have all have
47:23
different degree because the pairwise
47:24
combine combined together pairs of the
47:26
same degree making sure that all the new
47:28
trees have different degrees okay we
47:32
also know that the max degree is log n
47:34
so the permissible degrees are between 0
47:37
and log n so that most log n plus 1
47:40
possibilities okay so you can't have
47:45
more than log n plus 1 degrees after
47:47
you're done with the pairwise combined
47:56
yeah right this is a number of minimum
48:03
trees in a binomial heap okay and if if
48:06
every tree has to have different degree
48:08
then you can have only one tree of each
48:09
degree to have more than log n plus one
48:17
trees I've got to have two trees that
48:19
have the same degree which is not
48:21
possible because you just did the
48:23
pairwise combined it's like if if the
48:30
max degree is 3 you can have a tree of
48:33
degree 0 a tree of degree 1 a tree of
48:36
degree 2 and a tree of degree 3 there
48:37
four of them you do have five trees you
48:41
got to repeat one of these degrees
48:47
all right any other questions okay all
48:51
right so we stopped here