Transcript


00:11
okay alright just a reminder we have a
00:16
we have an exam scheduled for Friday of
00:18
next week the syllabus is posted on the
00:23
web there are sample tests you certainly
00:25
want to try out the sample test before
00:27
you should come for the actual test and
00:30
again there aren't really any surprises
00:34
there they shouldn't have been any
00:35
surprises in the first test if you'd
00:37
done the sample test you should have
00:39
done well on the first test that the
00:41
same will be true for the second one
00:43
okay all right today we're going to take
00:49
a look at the analysis for what about
00:51
split trees but before I start if you
00:54
have any questions is kind of a good
00:55
time to ask them No okay alright so in
01:03
the last lecture we took a look at splay
01:07
trees we saw that splay trees were
01:11
really a minor extension of unbalanced
01:14
binary search trees especially if you
01:16
took a look at the bottom up version you
01:18
could derive the code for bottom-up
01:21
split trees by adding one additional
01:24
function to unbalanced binary search
01:29
trees namely the splay operation and
01:31
then you insert code in your other
01:34
functions insert delete whatever to
01:37
invoke this play okay so while the
01:40
structure is very simple to describe in
01:42
code and the analysis isn't quite as
01:46
simple in fact we saw last time that the
01:50
worst case performance is actually
01:51
rather poor its order of n for most of
01:54
the operations so today what we want to
01:57
establish is that even though the
02:00
complexity on a per operation basis is
02:02
bad the structure in fact is rather good
02:05
for the majority of applications where
02:09
you don't really care how much time it
02:11
takes for an individual
02:13
search or an individual insert or delete
02:16
you care about how much time the whole
02:18
application takes to run and that
02:20
application may perform thousands of
02:22
insert searches and deletes so the time
02:24
across a sequence of operations okay
02:28
alright so we're going to show that the
02:35
actual and amortized complexity of the
02:39
joint operation is one fact in the joint
02:42
operation you don't really do a split
02:44
you just take two trees and the middle I
02:47
don't get a node and make these two
02:49
trees they're left and right children
02:52
the remaining operations have an
02:55
amortized complexity that's log n even
02:58
though their actual complexity is n now
03:05
in coming up with the amortized
03:10
complexity we'll make use of the
03:14
observation that the actual complexity
03:17
of any of these operations in fact even
03:21
this one is really governed by the
03:25
complexity of the Associated display now
03:29
certainly here there is no Associated
03:30
display okay so you can say that a null
03:33
splays older one and so the actual is
03:36
also once you're okay but if you look at
03:38
these operations search okay so you
03:40
start at the top of the tree you go down
03:42
and you spend some amount of time going
03:44
down but then asymptotically you spend
03:48
the same amount of time going back up
03:49
during the splay so if you measured only
03:52
the time spent on display asymptotically
03:54
we'd have the same result as if we
03:57
focused on both the downward pass and
03:59
the backward or bottom-up display pass
04:03
same is true for the other operations
04:05
because display always starts at the
04:07
deepest node you get to and it takes you
04:10
linear time to get to that deepest node
04:12
and then takes your linear time to
04:14
recover from the deepest node back up to
04:16
the root promoting the splay node okay
04:19
so it's sufficient to focus on the
04:23
amortized complexity of a splay
04:27
and that's what we do we'll look only at
04:29
the cost of this play now in performing
04:41
the amortized analysis we certainly have
04:44
a choice of method to use if you recall
04:47
we had three we had the aggregate method
04:49
the accounting method and the potential
04:52
function method and here we're trying to
04:55
get only the cost of one operation
04:57
display and so all three of these are
04:59
candidates the aggregate method really
05:03
wasn't a good candidate when we were
05:05
looking at binomial heaps of Fibonacci
05:06
heaps and things because we were trying
05:09
to arrive at different amortized
05:11
complexity results for different
05:13
operations but here there's only one so
05:16
you could think about using the
05:17
aggregate scheme or the accounting or
05:19
the potential and we'll use the
05:21
potential function here because this is
05:23
AK turns out to be the easiest scheme to
05:26
use in this case now to use the
05:33
potential function method you really
05:36
need to start with a guess on a
05:39
potential function and the only guidance
05:44
you have is that it should be a
05:45
non-negative function so once you guess
05:52
the potential function then we have a
05:53
well-defined methodology to start from
05:55
that guess use our knowledge of the
05:59
actual cost of an operation and the
06:01
potential change resulting from it to
06:03
arrive at the amortized complexity so
06:07
the trick here is to guess the right
06:09
potential function and there's really no
06:12
scientific way to do it you just get
06:14
something and see if you can arrive at a
06:17
bound that you think is right so the
06:20
function we're going to guess here is
06:22
going to use the notion of the size of a
06:25
subtree so the size of a subtree rooted
06:28
at X is just a number of nodes in that
06:30
subtree and then from the size we'll
06:34
compute something called the rank and
06:35
the rank is the floor of the log of the
06:38
size and again once you
06:41
go through the details of the proof it
06:43
makes a difference whether you use floor
06:45
and you use ceiling if you switch to
06:47
ceiling the proof doesn't go through if
06:50
you use floor this proof does go through
06:52
okay so we use the floor of the log of
06:55
the size as the rank of a node and then
06:58
the potential after you have done the
07:01
eye operation is the sum of the ranks of
07:04
the nodes so the these quantities size
07:17
and Frank are computed after you have
07:19
done the split so potential after the
07:22
eye operation you compute the rank of
07:24
the nodes after the operation and then
07:27
you add up across all of the nodes right
07:36
will by definition the potential will be
07:39
0 when you have no items ok there are no
07:44
nodes in the collection so there's
07:48
nothing that has a rank the sum is 0 now
07:55
actually since we support joins and
07:57
splits we really need to extend this
08:00
definition to not just one tree but a
08:03
collection of trees ok so you go to have
08:06
multiple search trees if you want to be
08:08
doing joins and when you do a split you
08:11
end up with multiple search trees so so
08:14
really even though I've written this out
08:16
as the sum across the nodes in a tree it
08:19
should probably be some across the nodes
08:21
some of the ranks across all nodes in
08:24
all trees ok all right so unless the
08:30
potential is the sum of the ranks of all
08:33
the nodes in the collection of search
08:35
trees that you have
08:44
let's look at an example alright so
08:49
first let's put down the size values the
08:51
size of the subtree rooted here is one
08:56
for this node there are two nodes in
08:59
that subtree so the sizes to three nodes
09:02
in the subtree rooted out here these
09:03
three nodes over there there's only one
09:07
and then the subtree rooted at 40 there
09:09
are two nodes the sizes two and at the
09:13
root the overall tree has a total of six
09:15
nodes so the size is six the rank is
09:21
just the floor of the log of the sizes
09:23
so the rank of this node will be zero
09:26
okay and and that's done base two over
09:30
here it will be 1 okay then the rank out
09:35
there is also 1 you get a 0 a 1 and then
09:40
for the root the rank is 2 right the
09:44
ranks have an interesting property that
09:46
as you go from one node to its parent
09:49
and grandparent the rank does not
09:51
decrease ok because the size keeps
09:55
increasing so the rank can't go down
09:56
of course the rank may not increase ok
10:00
so like you go from here to there the
10:01
rank hasn't gone up ok but rank
10:07
certainly doesn't decrease as you go up
10:09
the tree right the potential is the sum
10:16
of the ranks so we add up all these blue
10:17
numbers and you gather the potential is
10:20
5 all right so the potential is the sum
10:26
of the ranks of the nodes and in this
10:28
example I just have one tree but in
10:30
general you could have multiple trees so
10:32
you add up the ranks across all of the
10:34
nodes and all of the trees or any
10:38
questions were what potential function
10:41
we're using
10:52
alright the rank of the roof since the
10:55
size of the root is the number of nodes
10:57
or elements in the search tree if that's
10:59
n the rank of the root would be log n so
11:12
if you insert a node so if you insert a
11:22
node so for example let's say we insert
11:24
a 7 so it comes down here is the left
11:25
child of 7 you might ask yourself by how
11:28
much can your potential go up now the
11:35
number of nodes on this insert path
11:37
could be large in a splay tree it could
11:40
in fact be order of n ok so at first
11:46
glance you might think that well if
11:48
there are n nodes in the path then there
11:50
are n nodes whose rank could go up and
11:54
the rank can go up by at most 1 as a
11:57
result of an insert because the size
11:59
only goes up by 1 at each node so the
12:02
rank can go up by 1 so you might think
12:03
that the potential could go up by n but
12:08
in fact potential cannot go up by n
12:11
because the if you follow the sequence
12:18
of ranks ok so you got a rank of 0 okay
12:23
and then you got in this case a couple
12:26
of ones then you might have a few twos
12:28
and some threes and fours and you may
12:31
even skip some numbers on the way but
12:34
since the rank at the root is only log n
12:37
there are only log n plus 1 different
12:40
rank values ok and and these all come in
12:43
sequences ok so if you have a bunch of
12:46
ones for example here you got a 1 and a
12:48
1 well then this guy's size goes up by 1
12:51
but its rank can't go up because its
12:54
parent which had a bigger size still had
12:56
a rank of only 1 so if you increase this
12:58
guy's size his rank and go up yeah this
13:01
guy's size goes up by 1 but if
13:03
parents rank was one this guy's rank has
13:05
to stay one even though the size has
13:07
gone up okay so in these sequences it's
13:10
only the last guy in the sequence whose
13:12
rank can go up by one okay the number of
13:16
these sequences is only log n plus one
13:19
so they're only log n plus 1 nodes on
13:22
that insert path whose rank can increase
13:24
by one okay so the total increase in the
13:31
log in the rank can only be of the order
13:34
of log n so so even though the path is
13:44
long only a small number of nodes on
13:47
that path can see an increase in their
13:50
rank alright so there are log n plus 1
13:57
nodes whose rank can go up by one in
13:59
addition if you're looking at the
14:00
potential for the whole thing you put in
14:03
a new node here okay but that guy's rank
14:05
comes in at 0 okay so the total change
14:10
in potential of the tree is bounded by
14:12
floor of log n plus 1 or any questions
14:19
about that
14:33
all right you can make similar analyses
14:36
for other operations like if you do a
14:37
delete how does the rank I mean how does
14:40
the potential change as a result of it
14:42
delete or if you do a split how does the
14:45
potential change okay so across all of
14:52
the operations that you perform the
14:55
potential can change by at most log n
14:57
plus one in some cases the potential
14:58
will decrease all right so to arrive at
15:09
the amortized cost of a splay operation
15:12
will first take a look at an individual
15:14
splay step and see what does play step
15:19
costs so for a slips play step we had
15:22
three cases one was display node was now
15:27
or it was the root in that case you
15:29
didn't do any work okay so in that case
15:38
you make no changes to the tree so the
15:42
ranks of all the nodes stay the same so
15:46
there's no change in the potential okay
15:51
so you look at the potential before this
15:54
play and the potential after this play
15:55
since this play does nothing none of the
15:58
ranks in the tree change and so there's
16:02
no potential change so the amortized
16:06
cost by definition is actual cost plus
16:08
potential change and depending upon how
16:15
we measure the actual cost for this
16:17
operation we could say the actual cost
16:22
is zero because nothing is done or we
16:24
could say the actual cost is 1 because
16:27
we have to at least test for this
16:28
condition and then decide to do nothing
16:30
okay so depending on how you go we might
16:33
give this case a cost of 1 or 0
16:35
amortized cost it doesn't really matter
16:39
what you do because this happens only
16:40
once in each play operation
16:47
or the second case is when US plane out
16:50
is at level two and then you do a
16:52
rotation promoting this node to the root
16:54
level so we had this diagram for one of
16:59
the two cases that represent a level two
17:03
thing and then we start from this
17:05
configuration we end up over there so
17:09
what I'd like to do is I'd like to come
17:12
up with an expression for the change in
17:14
potential then I can add that to the
17:19
actual cost okay the actual cost of this
17:22
operation is one because we change a few
17:24
pointers to effect this rotation okay so
17:29
I take the actual cost added to the
17:31
potential change I get the amortized
17:32
cost for this step so to figure out the
17:38
change in potential I need to identify
17:40
which nodes in my tree might have a
17:43
change in rank and then figure out how
17:46
much that change in rank is and add up
17:47
all the rank changes you know the nodes
17:53
in this subtree a the size for those
17:57
fellows doesn't change because of this
17:58
rotation okay similarly for the fellows
18:01
and B and then C those sub trees every
18:05
node in those sub trees has the same
18:06
size here as it does on that side so
18:10
their ranks are unchanged the only nodes
18:13
whose rank could change the rank of Q
18:16
can change because this size here is
18:18
size of a precise of B plus one but the
18:22
size out here is more in addition to a
18:26
and B and that one you've got this node
18:28
and C so the rank of Q could have
18:32
changed it may not have changed because
18:35
you're doing the log of the flaws it may
18:37
not have but it could have changed and
18:38
if it changed it would have gone up and
18:42
the rank of P could have changed it
18:45
could have gone down
18:49
so we need to figure out how much the
18:51
rank of Q and P might have changed or
18:53
actually how much did the some of the
18:55
ranks of P and Q change alright so since
19:02
we have to talk about the rank of a node
19:04
before the rotation and after the
19:07
rotation or before this place step and
19:09
after we'll introduce a notation for
19:11
that so our X will represent the rank of
19:14
the node X before you do this play step
19:17
and our prime will give the rank after
19:20
the step ok so R is the rank on this
19:24
side our prime is the rank on that side
19:30
alright so the change in potential for
19:33
our entire collection of nodes is the
19:37
ranks of P and Q after - the ranks of P
19:41
and Q before ok so I said a little while
19:53
ago that the rank of P as a result of
19:56
this transformation may go down so the
19:59
our prime of P may be smaller than our P
20:02
and so if I take the R prime P minus our
20:06
P term and throw it out if I throw these
20:08
two things out I may be left with a
20:10
bigger item than what I started with
20:12
I may be left with the same value or
20:15
something bigger so I get this
20:17
inequality the change in potential is at
20:19
most a change in the rank of Q and from
20:28
that I obtain a an expression for the
20:32
amortized cost of promoting somebody by
20:36
one level and that turns out to be the
20:39
actual cost is one changing a few
20:41
pointers plus the rank change in Q
20:44
display note
21:10
right now let's go to the final case
21:14
which is two-level moves because this
21:17
breaks down into four sub cases the LLL
21:19
RRR RL and we'll just take a look at one
21:24
of these cases and even for this case I
21:27
won't go through the entire derivation
21:30
I'll just do an approximate analysis and
21:33
then refer you to the book for the fine
21:34
details all right so this is the before
21:39
configuration that's the after
21:40
configuration it's only the ranks of
21:44
display node its parent and its
21:46
grandparent that change as a result of
21:48
this transformation everybody else's
21:51
rank is the same so the potential change
21:54
is just the rank of QP + GP after the
21:58
operation - their ranks before the
22:00
operation
22:19
all right to simplify that expression
22:21
I'll make use of some relationships from
22:25
here the first one we'll use is that the
22:28
rank of Q on that side is the same as
22:30
the rank of GP on this side because the
22:33
size is the same so the size of GP here
22:39
it includes these three nodes plus
22:43
everybody in ABC and D the same is true
22:46
out here the size of Q is these three
22:49
nodes plus everybody in ABC and D okay
22:51
so the size of GP on the left is the
22:55
same as the size of Q on the right so
22:57
the rank of GP before the operation is
22:59
the same as the rank of Q after the
23:01
operation the rank of P are prime P is
23:08
less than equal to our prime Q the
23:12
subtree rooted here is a subtree of this
23:15
fellow so the size up here is bigger
23:18
than the size there okay so the rank up
23:21
here is at least as big as the rank
23:24
there or as I said earlier if you move
23:27
up the tree ranks don't go down okay all
23:31
right so the rank of P after the
23:33
operations less than equal to rank of Q
23:35
after the operation same reasoning here
23:40
our prime of GP has to be less than
23:44
equal to our prime of P which is less
23:45
than a go to our prime of Q then a
23:53
similar equation from this side the rank
23:55
of Q is less than equal to rank of P so
24:02
I'll make use of these four
24:04
relationships
24:05
to simplify the potential change
24:07
expression I had on the previous slide
24:12
right so that was the expression and
24:14
here are my four
24:19
relationships okay
24:23
so I'll use this one here to get rid of
24:26
our prime P and our GP because you got
24:30
an R prime P sorry an R prime Q minus an
24:35
r GP so I can subtract them off the
24:41
equal then I'll use this one here I'll
24:48
replace this with our prime Q
24:50
potentially getting a bigger item here
24:52
making this a less than equal
24:54
relationship I'll use this one to
25:00
replace our prime P making the right
25:04
side potentially bigger I'll use this
25:08
one to get rid of our P okay we're
25:14
subtracting now a smaller item
25:16
potentially again making the right side
25:19
potentially bigger so by making those
25:27
changes I can change the right hand side
25:30
so that it contains only Q's okay
25:34
so I get a relationship that looks like
25:37
this so the change in potential okay so
25:41
that becomes an R prime Q this one
25:44
becomes an r prime Q then I get an r q
25:47
and r q the change of potential is at
25:52
most two times the change in the rank of
25:54
Q
26:15
and actually if we break this analysis
26:20
that we just did down into some cases we
26:23
can show a tighter result which looks
26:26
like this that the change in potential
26:28
is at most three times the change in the
26:31
rank of Q minus 1 right this thing comes
26:39
from the previous equation so here if R
26:50
prime Q is not equal to R Q ok then the
26:53
difference has got to be at least one in
26:56
which case the second equation follows
26:59
so the only time the second one doesn't
27:02
come from here is when our prime Q
27:03
equals our Q so you got to have a
27:07
separate proof for the case when our
27:10
prime Q equals our Q to show that in
27:12
fact in that case the right hand side
27:16
given here is the right one and that
27:21
proof is there in the book there's a
27:23
separate proof for our prime Q equals
27:25
our Q to show this alright so once we
27:34
have this ok the amortized cost of a
27:42
two-step move for the ll case then
27:46
becomes its actual cost plus potential
27:48
change the actual cost is one you change
27:52
some number of constant number of
27:53
pointers that's the potential change so
27:56
the plus one cancels after the minus one
27:58
you end up with this term here
28:21
all right the the the the loss of this
28:28
one here is really important this is
28:31
what makes this proof goes through the
28:33
fact that you don't have any additive
28:35
one here if I go back a few slides and
28:38
take a look at what I had for a one step
28:42
move okay let's go back and take a look
28:44
at that
28:56
okay right if I look at this formula
29:02
here okay right what is bad about it is
29:07
this plus one okay the reason that plus
29:11
one is bad is that if you think of
29:16
yourself as sitting deep down in a tree
29:18
doing these one-step moves one at a time
29:20
okay the number of these one-step moves
29:23
could be N or n minus one okay so I take
29:29
the sum of these bounds I'm going to end
29:31
up with an end term on the right hand
29:33
side and most of these hours will cancel
29:35
out okay so you'll end up with like an N
29:38
plus the final rank of Q minus the
29:41
initial rank of Q the final rank of Q
29:44
would be log N and the initial rank of Q
29:47
could be zero
29:48
okay so that difference is log n which
29:50
is okay but we've got this additive sum
29:52
of n showing up so the amortized cost of
29:56
this play becomes n that's the best you
29:58
can derive if you do only one level
30:01
moves and that's because you got this
30:03
little one sitting out there okay
30:06
but in the two level moves we don't have
30:10
that additive one sitting out there so
30:12
when I do the same analysis there
30:27
so when I do the same thing here which I
30:30
will in a moment if you look at you do a
30:33
two level move another two level move
30:34
when you try and add up these
30:36
differences again all of these are prime
30:40
terms in the middle will cancel out and
30:41
you'll be left with three times the
30:43
final rank minus the initial rank okay
30:47
and the final rank is log n initial
30:48
drank may be zero so you got three log n
30:51
okay so that that's the reason you don't
30:55
do one level moves alone because with
31:00
one level moves because of that additive
31:02
one in the amortized cost for a step the
31:06
cost of a entire splay operation becomes
31:09
n okay all right then there are other
31:15
cases there's the RL case and there's
31:18
the LR and things they all have the same
31:21
type of flavor in the analysis all right
31:26
now let's look at this play operation as
31:28
a whole alright so a splay operation
31:39
consists of making some number of two's
31:41
level moves followed by potentially a
31:45
one level move so if you look at all the
31:52
two level moves let's suppose that our
31:55
double prime is the rank of Q after the
31:58
last two level move and our triple prime
32:04
is the rank of Q after you do the one
32:08
level move let's assume there is a one
32:11
level move
32:16
all right so all of the two-level moves
32:19
together cost you this okay the first
32:22
one cost you like our prime - are the
32:26
next one will cost you the new are - the
32:28
art prime but that our prime will cancel
32:30
with the previous our prime because you
32:32
get kind of a telescoping sum as you add
32:34
up across all of the two-level moves and
32:35
so what you end up with is the final
32:39
rank of Q after the last two-level move
32:42
- the initial and then you got this
32:44
multiplying factor of three alright so
32:55
the amortized cost of the splay
32:57
operation is the cost of all the
33:04
two-level moves
33:05
plus the cost of that one level move
33:08
that you do in the end assuming you do a
33:10
one level move so this is the cost of
33:12
that one level move the final rank of Q
33:15
the rank of Q just before the one level
33:17
move and then you've got all those two
33:19
levels moves right this term here is
33:27
non-negative okay it could be zero there
33:30
could be no change in rank okay but it's
33:33
not going to be a negative term okay
33:37
when you move a node up the rank might
33:39
change if it does change it will
33:41
increase so I can potentially get a
33:47
bigger one term by multiplying this
33:49
difference with three and now the R
33:57
double prime cancel out
34:07
okay the final rank is that most log of
34:12
the number of items that you have and of
34:19
course the initial rank could at most be
34:22
good at worst b0 can be lower than that
34:25
so the amortized cost of a splay
34:28
operation is at most three log n plus
34:30
one all right so we looked at the cost
34:44
of a splay operation and the way we
34:47
measured the amortized cost of a splay
34:49
operation is really the change in
34:52
potential as defined by potential just
34:55
after the splay operation minus the
34:57
potential just before display operation
35:01
now our intent is to use this to say
35:03
that a cost of a sequence of operations
35:05
that most the length of the sequence
35:07
times the amortized cost over splay now
35:12
one problem with doing that is that when
35:19
we did our initial analysis we're back
35:21
in probably lecture 1 or lecture 2 of
35:23
this semester we said when you go
35:26
through the sequence you get a
35:27
telescoping sum and all you're left with
35:29
is potential at the end - potential
35:31
before okay now a problem out here is
35:35
when we go through this sum we don't get
35:39
that telescoping sum with everything
35:42
disappearing and we don't get that
35:45
because potential is changing here not
35:49
just because this play but because of
35:50
the operations themselves and we haven't
35:53
accounted for that so it's like
35:54
somebody's putting money in the bank for
35:56
us and we're spending without accounting
36:00
for the inflow of money so when we do an
36:03
insert potential goes up okay so to get
36:10
a clear idea what's happening okay so
36:12
the actual cost of a sequence of
36:14
operations okay
36:17
we'd like to say is well we know this is
36:21
the case okay it is the actual cost of
36:25
the Associated splays so the same order
36:28
in fact it may be two times the cost of
36:31
the Associated its place okay so the
36:36
actual cost of the aisle display by
36:38
definition is the amortized cost of the
36:41
aisle display - the change in potential
36:43
resulting from the ayats play so we've
36:49
shown that the potential change is this
36:51
much okay
36:52
oh so we've shown this is the amortized
36:56
cost okay and the potential changes the
37:00
potential just after the eyuth operation
37:04
which I'm calling P Prime okay minus P I
37:15
sorry P Prime
37:17
I is the potential just before you do
37:23
this play okay and P I is the potential
37:26
just after you've done this places just
37:28
after the operation okay so P prime is
37:32
the potential just before this play okay
37:34
that's how we derived the amortized cost
37:38
of us play we looked at at the potential
37:40
just before this play and the potential
37:43
just after this play which is not the
37:45
same as the potential before the entire
37:48
operation because the operation included
37:52
doing some other work which move nodes
37:54
around like an insert added a node and
37:57
so if you look at P I minus 1 which is
38:02
the potential just after the I minus
38:05
first operation it's not the same as the
38:07
potential just before this play because
38:09
in between we added a node we change
38:12
that potential okay all right so
38:21
there's this relationship which says
38:24
that the potential just before the eyuth
38:27
operation sir just before the eyuth
38:30
splay okay is related to the potential
38:35
just after the i- first operation by
38:40
this additive term because you may have
38:43
increased the potential as a result of
38:45
an insert suppose you may have decreased
38:48
the potential to but the worst that can
38:49
happen to you is the potential may have
38:51
gone up by that amount and if you really
38:55
want to be very accurate we said it
38:57
could go up by that plus one probably
39:04
all right so we have that relationship
39:06
and all right so now i I'm doing some
39:17
simplification here we had this in a
39:18
previous slide I'm just taking that our
39:20
Q term and saying I can dispense with
39:24
that that will it most increase this
39:25
whole thing okay now I take the P prime
39:33
I and replace it by a potentially larger
39:35
value which is P I minus 1 plus floor of
39:39
log I okay so it becomes instead of
39:46
three it becomes four times the floor
39:48
plus P I minus one and that accounts for
39:55
infusion of funds into my bank account
39:58
that I hadn't accounted for before but
40:03
it doesn't really change the picture
40:04
much okay so if you now do the sum of
40:11
the actual costs of displays okay so now
40:15
you get a telescoping sum so you
40:16
previously I had a P Prime and a P i
40:19
okay so as you do this four different
40:21
eyes you got a bunch of P prime sand got
40:23
a bunch of peas and nothing cancels out
40:25
okay so having changed the P Prime's to
40:29
P's now everything cancels out except
40:31
for the first and the last P
40:35
so this term here gets multiplied by n
40:39
as you go through n operations oh and
40:43
then you get a p0 and a PF so p 0 0 PN
40:55
is non-negative so we can throw out the
40:59
p0 minus PN term then I've got this n
41:03
term which is no bigger than n log n so
41:05
I put an a make it a 5 n log n alright
41:12
so the amortized or some of the actual
41:14
costs of all of this plays is bounded by
41:17
something like 5 times n log n all right
41:29
any questions
41:38
yeah KP 0 is 0 and PN is non-negative
41:47
okay so potentially here this whole
41:51
thing is a negative number and we throw
41:52
away the negative number you get a
41:54
bigger residue okay so that's okay
42:03
alright so in most of these structures
42:11
where the amortized complexity is good
42:13
the structure tends to be fairly simple
42:17
in terms of coding of stuff which the
42:18
analysis that's hard to do and this is
42:23
the last amortized analysis we're going
42:26
to see in this class okay there aren't
42:34
any questions we'll stop here
42:45
you