This note resolves the part of the 2nd lecture on link cut trees that was left unresolved during the lecture. I think this is the cleanest way to finish this up. First of all, we'll use the standard potential function for splay trees. Phi(T) = Sum r(x) x in T Recall the Access Lemma: The amortized number of rotations done by a sequence of splays is at most 3(r(root) - r(x)) + 1 Remember that the +1 was for the last rotation, which might happen if the splay ends in a zig step. So let's separate the rotations that occur in splaying into two types "top rotations" and "non-top rotations". The top ones are those which occur in the zig step. So a slightly refined version of the Access Lemma says this: In a sequence of splays, here are amortized bounds: number of non-top rotations <= 3(r(root)-r(x)) number of top rotations <= 1 So consider the cost of a splay(x) in the virtual tree. We'll let this cost be the number of edges on the path from x to the root of the virtual tree containing x. This is also precisely equal to the number of rotations done in the 3-part splay(x) operation. Phase 2 (the splices) does zero rotations so its cost is zero. Let's consider the two types of rotations separately. In phase 1, the telescoping argument explained in lecture shows that the number of non-top rotations is at most 3log(n). In phase 3 the number of non-top rotations is also at most 3log(n). What about the top rotations? In phase 1 we do at most k+1 of these (k is the number of dashed edges on the path). In phase 3 we do at most 1 of these. So we need to bound Sum(k+2) where the sum is taken over all splay operations in the virtual tree. Note that in phase 3 we also do k-1 non-top rotations. Therefore, the total number of non-top rotations done is an upper bound on Sum(k-1) over all the splays. (where the sum is taken over all splays in the virtual tree.) Therefore Sum(k-1) <= Sum(6log(n)) ==> Sum(k+2) <= Sum(6log(n)+3) ==> amortized number of top rotations <= 6log(n)+3 So the amortized number of rotations total is at most 12 log(n) + 3. Q.E.D. ---Danny Sleator October 21, 2009