From:callahan@condor.cs.jhu.edu (Paul Callahan)Newsgroups:comp.theorySubject:Jordan Sorting with Splay Trees conjectureDate:12 Aug 1995 13:40:08 -0400Organization:The Johns Hopkins University CS Department

Jordan Sorting is the problem of sorting a list of numbers by x-coordinate, assuming that the numbers represent intersections of a non-self-intersecting (i.e. Jordan) curve with the x-axis, and that they are given in the order that they appear along this curve. It has been known for about a decade (as far as I my research has determined) that Jordan Sorting can be performed in linear time. What I'm curious about is the following conjecture given in a paper that presents a linear time algorithm (reference given below): Our second remark is that there may be a much simpler way to sort Jordan sequences in linear time: we merely insert the items in the sequence one-at-a-time into a splay tree ... and then access them in sorted order. ... On the basis of Sleator and Tarjan's dynamic optimality conjecture, we conjecture than this sorts Jordan sequences in O(n) time. This is from "Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees" (Hoffman, Mehlhorn, Rosensteihl, and Tarjan, _Information and Control_ 68 (1986) pp.170--184). Several later papers claim to present simpler algorithms, but the most recent one I've seen (1990) is still not nearly as simple as the approach using splay trees. So, I'm curious if this conjecture has been treated either theoretically or experimentally. From a theoretical perspective, one would think that if the conjecture is true, it would at least be easier to prove than the dynamic optimality conjecture, and would still be a pretty interesting result. It strikes me as even more attractive as an experimental issue, though, because there is existing code for splay trees, and random Jordan sequences are not hard to generate (of course, this leaves open the issue of generating "hard" cases of Jordan Sorting). In a sense, there's no excuse at all for not performing this experiment. My literature search was far from exhaustive, so if there are experimental results, I'd very much appreciate a reference. It seems to me that if the conjecture is actually true, then one could perhaps make a careful study of the splay tree algorithm for Jordan Sorting and try to infer what it is doing to achieve such good results. This would provide a non-trivial linear time algorithm that in some sense "exists in nature" rather than being the consequence of clever design. If true, that strikes me (and some other people, I hope) as quite remarkable despite the fact that it would do no better than a known optimal algorithm. -- --- Paul Callahan --- callahan@cs.jhu.edu --- "The first principle in science is to invent something nice to look at and then decide what it can do." -- Rowland Emett

From:callahan@biffvm.cs.jhu.edu (Paul Callahan)Newsgroups:comp.theorySubject:A family of Jordan Sequences for which Splay Sort is Omega(n log n)Date:25 Sep 1995 14:13:09 -0400Organization:The Johns Hopkins University CS Department

About a month and a half ago, I posted an inquiry about a conjecture related to sorting Jordan sequences. A Jordan sequence is a list of intersections of a non-self-intersecting plane curve with the x-axis. The Jordan sequence sorting problem is to sort these intersections by x coordinate. The non-crossing-curve restriction implies that the number of Jordan sequences of n values is O(c^n) for some c, rather than n!, implying that a general-purpose comparison-based sorting algorithm may not be optimal. In fact has been known for over a decade that Jordan sequences can be sorted in O(n) time using only comparisons (I emphasize the point about comparisons to avoid getting mired in the MSD-radix-sort flame war now in progress). Anyway, there is an appealing conjecture in two of the papers presenting linear time algorithms (Information and Control, 68 170-184 (1986) and Information Processing Letters 35 85-92 (1990)) that if the values in a Jordan Sequence are simply inserted into a splay tree, and read off in sorted order, then this might also require O(n) time in the worst case. This general technique is usually called Splay Sort, and can for certain kinds of input be shown to require much less time than a worst-case optimal comparision-based sort such as Mergesort. If I understand the Jordan Sequence conjecture correctly, I can show that it is incorrect. I don't know if the following result is new, but it's fairly specialized and doesn't seem to lead anywhere, so I'm posting it here after wondering for about a month what to do with it. Because this posting not a formal publication, I'm going to leave out some steps. It should not be too hard to fill in the details. First, to prove a lower bound on sorting a sequence using Splay Sort, it will suffice to prove a lower bound for any algorithm that uses insertions into a binary search tree using any rotation strategy. In fact, the more general kind of lower bound is often easier to prove than a lower bound for Splay Sort itself, owing to the work of Robert Wilber in FOCS '86 (revised version in Siam J Comp vol. 18 no. 1), which provides two powerful methods for showing lower bounds on accessing sequences of values in Binary Search Trees. We will not really need these methods here, but only the corollary that accessing the nodes of a binary tree containing the values 0,1,...,2^k-1 in bit-reversed order (i.e. taking the binary representations of these values in increasing order but reversing the "significance" of the bits) requires Omega(k 2^k) rotations In the following, I'm going to use the claim that sorting a sequence by inserting it into a binary tree is as hard as accessing the same sequence in a tree containing these values. I haven't proved this, but it seems to me that each time a value is inserted (a new leaf added at what was a "null pointer"), one could imagine that that value already existed as a node in the tree but had not previously been accessed. It should thus be possible to construct an initial tree containing the values to be sorted for which the rotation sequence is the same whether one is inserting into an intially empty tree, or accessing from an initally full tree. (Originally, I had a more complicated idea for a proof that would not require this claim but I think it is true, and it results in a cleaner argument). Now, what remains is simply to construct a family of "hard" Jordan Sequences such that for any value of n there is a sequence in this family containing at least n elements. As it happens, the sequences in this family will bear a relationship to bit-reversed order that will cause them to require Omega(n log n) rotations to sort using any binary search tree, according to the result of Wilber. First I'll give an intuitive explanation of where these sequences come from. If one were to take a looped, flattened out strip of paper and view it facing the edge, this would look like a very simple Jordan Curve. I.e.: +---------------------------------------+ | | +---------------------------------------+ (unfortunately, ASCII graphics make it unclear, so let me repeat that this is viewed on edge, not from above, as it might also appear). If this is folded over on itself to double its thickness, we get another Jordan Curve, but which is somewhat more convoluted. I.e: +-------------------+ | | +---------------+ | | | +---------------+ | | | +-------------------+ We can repeat this "doubling over" process as many times as we like, each time doubling the number of intersections of the curve with a vertical line. For larger examples, it becomes more convenient to represent the shape of the curve using two sets of matching parentheses (this is the representation normally used to prove a bound on the number of Jordan Sequences). E.g., if we double over two more times, and rotate 90 degrees so the curve intersects the x-axis, we obtain: (((((((()))))))) ()()(())(((()))) Matching parentheses in the top sequence with arcs above and those in the bottom sequence with arcs below gives us the actual curve. To connect this idea with bit-reversed order, we will describe the folding process as a transformation on a sequence of numbers that will denote the actual Jordan Sequence in question. The correspondence to folding is not too hard to see, but will be omitted here, since it is not really needed once we obtain the final form of the construction. First, in the original loop, the sequence of intersections is the same both on the curve and on the intersecting line, so we denote this sequence 0 1. Now, given such a sequence, we obtain the next, doubled over, sequence as follows: (1) double each number in the sequence (2) append the new sequence to its own reverse (3) Add 1 to every odd-positioned number in the sequence (the leftmost position is considered even). E.g. 0 1 --> 0 2 by (1) --> 0 2 2 0 by (2) --> 0 3 2 1 by (3) 0 3 2 1 --> 0 6 4 2 --> 0 6 4 2 2 4 6 0 --> 0 7 4 3 2 5 6 1 0 7 4 3 2 5 6 1 --> 0 14 8 6 4 10 12 2 --> 0 14 8 6 4 10 12 2 2 12 10 4 6 8 14 0 --> 0 15 8 7 4 11 12 3 2 13 10 5 6 9 14 1 etc. Here I'll resort to "proof by example" and simply point out that if you take the increasing sequence: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 and connect pairs of numbers adjacent in the sequence obtained in the process above with non-crossing arcs (also connecting the end values 0 and 1) you will obtain the Jordan Curve determined by the set of matching parentheses given earlier. Recall that for the lower bound, we want to connect this in some way to bit reversed order. So, yet another way to obtain the above sequence is to define the following function f on k-bit binary numbers denoted B = b ... b k-1 0 In the following, assume "+" denotes exclusive-or, and let f(b ... b ) = (b + b ) (b + b) ... (b +b ) b0 k-1 0 1 0 2 0 k-1 0 In other words, reverse the order of bits 1 through k-1, keeping b 0 in the same position. Also, if b = 1, then invert bits 1 through k-1. 0 E.g., B f(B) --- --- 000 000 001 111 010 100 011 011 100 010 101 101 110 110 111 001 Now, to get the kth sequence determined by the process given previously, we merely take the values i = 0,...,2^k-1 expressed in binary, and apply the function f to each i in increasing order. (We overload the meaning of f(i) to denote the result of converting i to a binary string, applying f, and converting it back to an integer.) It can be seen that from the above table, the sequence for k=3 is 0 7 4 3 2 5 6 1, which corresponds to that obtained previously. I imagine a lot of readers on this newsgroup don't find examples very convincing, no matter how large they are and how nicely they work out. Fortunately, once the function f has been defined as above, it suffices to show only that the sequence f(0), f(1), ..., f(2^k-1) is a Jordan Sequence, which is an easier task than showing it corresponds to the particular Jordan sequences illustrated earlier. To do this, it is necessary to show that if the numbers 0,1,...,2^k-1 are written in order left to right, then adjacent numbers in the sequence f(0),f(1), ..., f(2^k-1) can be connected by non-crossing arcs alternating above and below the list of numbers. A key observation needed for such a proof is that two arcs, one from a to b, and another from c to d cannot cross so long as a+b = c+d. The other is that they cannot cross if a < b < c < d. The set of arcs from a to b can be put in k+1 equivalence classes according to a+b, so that there is no crossing within each equivalence class. The second observation can then be used to exclude crossings between arcs in distinct equivalence classes. So, if I were writing a more rigorous article, it would now say something like "Lemma: For all k>0, the sequence f(0),f(1),...,f(2^k-1) is a Jordan Sequence." This would be followed by a proof, which is here left as an exercise. What remains is to show that it requires Omega(k 2^k) comparisons to sort such a sequence using Splay Sort. This can be seen by considering only those f(i) such that i is even. Let R(i) denote the result of reversing the order of the bits in the binary representation of i. By definition of f, we know that for even values of i, f(i)=2*R(i/2), so the subsequence f(0), f(2), ..., f(2^k-2) must be in bit-reversed order. Since the sequence f(0),f(1),...,f(2^k-1) contains 2^(k-1) elements in bit-reversed order, the result of Wilber implies that the time to access such a sequence in a binary search tree is Omega((k-1)2^(k-1)), and this also provides a bound on the time to sort the sequence using Splay Sort. Then, it follows that there exists a c such that for any value of n, one can construct a Jordan Sequence of length greater than n that requires c n log n comparisons to sort using Splay Sort, refuting the conjecture (as I understood it) that Splay Sort is a linear time algorithm for sorting Jordan Sequences. -- --- Paul Callahan --- callahan@cs.jhu.edu --- "The first principle in science is to invent something nice to look at and then decide what it can do." -- Rowland Emett

From:rew@lightstone.com (Bob Wilber at PUMICE)Newsgroups:comp.theorySubject:Re: Jordan Sequences for which Splay Sort is Omega(n log n)Date:27 Sep 1995 15:57:48 -0500Organization:UTexas Mail-to-News Gateway

Paul Callahan showed that a bit reversal permutation can be imbedded in a Jordan sequence. >In the following, I'm going to use the claim that sorting a sequence by >inserting it into a binary tree is as hard as accessing the same >sequence in a tree containing these values. I haven't proved this, >but it seems to me that each time a value is inserted (a new leaf >added at what was a "null pointer"), one could imagine that that value >already existed as a node in the tree but had not previously been >accessed. It should thus be possible to construct an initial tree >containing the values to be sorted for which the rotation sequence is >the same whether one is inserting into an intially empty tree, or >accessing from an initally full tree. This is the crux of the matter -- can the lower bound in [1] be used to get an an Omega(n log n) lower bound on Jordan sorting via insertion into a symmetrically ordered binary tree? That lower bound assumed that all elements are in the tree at the start, that they are being accessed in some specified order (allowing rotations in the tree), and that no insertions or deletions are done. >(Originally, I had a more >complicated idea for a proof that would not require this claim >but I think it is true, and it results in a cleaner argument). I believe your claim is false. But I think the lower bound can be patched up to work for this case. Consider how Jordan sorting with a binary tree proceeds: First, we traverse the simple closed curve, each time we encounter an intersection with the x axis, we insert that intersection point into a binary tree that is symmetrically ordered by the x coordinate. Second, we access the items in the tree, in order by x coordinate. At the end of the first pass the items are sorted by x coordinate, so the second pass accesses the nodes in sequential order. This pass takes linear time, including when the splay algorithm is used to do the accessing, as was proved by Tarjan [2]. So any lower bound must be applied to the first pass, when the items are being inserted. I find it convenient to "reverse the film" -- items are inserted into a tree in sequential order by x coordinate, in linear time, and then they are deleted in the order they appear on the curve (that is, deleted according to a Jordan sequence). We want to show that the deletion phase takes n log n time. We need to extend the model to allow for deletions. I think the following definition covers all the cases: Definition: A *standard deletion* of a node v can occur when v has at most one child. In that case, if v has no children (it is a leaf) it is simply removed. Otherwise v is removed and v's only child is made a child of v's parent (if v was not the root) or is made the root (if v was the root). In general, to delete a node v you do some sequence of rotations so that v has at most one child, and then you do a standard deletion of v. For example, as I recall deletion of a node v in a splay tree proceeds as follows: 1. v is splayed to the root and removed, leaving its left and right subtrees, L and R. 2. The largest node in L, r, is splayed to the root of L. 3. R is made the right subtree of r. This can be cast into the "standard model" as follows: 1. v is splayed to the root. Its left subtree is L. 2. The largest node in L, r, is splayed to the root of L, making r the left child of v. 3. r is rotated over v. 4. v has no left child; a standard deletion of v is done. Clearly this has the same complexity as the usual deletion routine. In the model when we delete v we must also count the cost of accessing v from the root. In order to fold all the costs into rotations, we require that the algorithm be "normalized" so that before deleting any node it first rotates that node to the root. This can always be done without increasing the time by more than a constant factor, because if the original algorithm does a standard deletion of some node v at depth d, it could first rotatate v to the root, then rotate v back to where it was (using 2d - 2 rotations), and then delete v. The cost of the extra rotations is just a constant times the cost of following the path from the root to v. Likewise a look up of v is always done by rotating v to the root. Two lower bound methods were given in [1], I will only patch up the first one (both methods give an Omega(n log n) bound for accessing the bit reversal permutation). It is important to understand that the intuition behind both lower bounds is that items you access "get in the way" of items that you want to access later, and must be rotated over. But if you can delete nodes, you can sometimes get a node v out of the way by deleting it, which might be cheaper than forcing several nodes "underneath" to rotate over v. So the ability to shrink the tree as you go might invalidate the lower bounds given in [1]. Here's a very quick review of the first lower bound method. We have some binary search tree T, whose n nodes may be considered to be consecutive integers. We allow rotations and standard deletions on T. A lower bound tree Y with 2n - 1 nodes is constructed whose leaves are the initial nodes of T and whose internal nodes lie between nodes in T, that is, they may be taken to be half integers. T changes through rotations and deletions but Y is fixed. For getting the lower bound on the bit reversal permutation Y is taken to be a balanced binary tree. The sequence of nodes in T to be accessed is s[1], s[2], ..., s[m]. (A node is "accessed" if we either look it up or delete it; in both cases such a node must be rotated to the root in a normalized algorithm.) Given numbers x<y, s{x, y} is the subsequence consisting of those s[i]s that are in the interval [x, y]. For each internal node u of Y, a score l(u) is computed as follows: Let x and y be the minimum and maximum leaves of the subtree rooted at u, and let s' = s{x, y} and let m' be the length of s'. Then l(u) = |{ i in [1, m'] | (s'(i) < u and s'(i+1) > u) or (s'(i) > u and s'(i+1) < u) }|. That is, l(u) counts how many times the subsequence s' hops from the left subtree of u to the right subtree, or vice versa. The sum of the l(u)'s is a lower bound on the number of rotations that must be done to access sequence s, if no deletions are done. A key part of the argument is that if s(i) < u and s(i+1) > u, then at some point between the access of s(i) and the access of s(i+1) there had to be a rotation of some node c > u over some node d < u. Furthermore, such a rotation has no affect on the generalized subtrees T{x, u} and T{u, y} corresponding to the leaves of u's left and right subtrees, so it is not already counted in the scores of u's children. (See [1] for the definition of a generalized subtree.) But suppose now that we allow standard deletions. If, for example, s(i) is at the root, has s(i+1) as its right child, and has no left child, then after accessing s(i) we can access s(i+1) simply by deleting s(i). No rotations had to be done at all. One might try to fix this by counting deletions of nodes in [x, y] in the score l(u), but this doesn't work because such such deletions would be doubled counted in some of u's children. In other words, either T{x, u} or T{u, y} is affected by any deletion of a node in [x, y]. To fix the lower bound note that if there is some j > i such that s(j)<s(i), then even if s(i) is deleted it has to be the case that between the access of s(i) < u and the access of s(i+1) > u there's going to be a rotation of a node c > u over a node d < u. (Use the first rotation after the access of s(i) that causes s(j) to have an ancestor that is > u; no standard deletion can cause this to happen.) Given sequence s of length m, say that i in [1, m] is an *end access* for s if either s(j) > s(i) for all j in [i+1, m] or else s(j) < s(i) for all j in [i+1, m]. That is, i is not an end access if for some j1, j2 > i, s(j1)<s(i) and s(j2)>s(i). Intuitively, end accesses are the nodes we can get out of the way by deletion. Modify the score for u as follows: l'(u) = |{ i in [1, m] | ((s'(i) < u and s'(i+1) > u) or (s'(i) > u and s'(i+1) < u)) and i is not an end access in subsequence s'}|. Now the lower bound goes through, using l'(u) rather than l(u), because we only count a rotation for u when s(i) < u and s(i+1) > u, and there is some j > i with s(j) < u. (Or else s(i) > u and s(i+1) < u, and there is some j > i with s(j) > u.) For the bit reversal permutation it is convenient to index the sequence from 0, so that s(i) = bit_reversal(i). For a bit reversal sequence on k bits, it is easy to show that there are only k+1 end accesses. These are at those j elements s(i) equal to 2 - 1, for some j in [0, k]. So the score assigned to a node u at the j'th level of the lower bound tree, whose subsequence is a bit reversal permutation on j bits, is j l'(u) = 2 - 1 - (j + 1). k-j The j'th level of Y has 2 nodes, so summing all the scores we get __ \ k-j j k L = /_ 2 * (2 - j - 2) = (k-4)*2 + k + 4. 1<j<k k With n = 2 , this gives an Omega(n log n) lower bound. So any algorithm that sorts a Jordan sequence by inserting the elements into a binary tree, maintained via rotations, requires n log n time. Note that at any single internal node u of the the lower bound tree the subtracting out of the end accesses can cause a radical reduction in u's score. For example, if the subsequence for u = 10.5 is 1 20 2 19 3 18 4 17 5 16 6 15 7 14 8 13 9 12 10 11 then l(u) = 19 but l'(u) = 0. Indeed, if the nodes are in the following "zig-zag" binary tree 1 \ 20 / 2 \ 19 / 3 \ ... They can be accessed in the stated order solely through standard deletions, with no rotations. Question: Are there sequences of n nodes where the lower bound for accessing with deletions is d(n) and the lower bound for accessing without deletions is not O(d(n) + n)? Such a sequence will need many end accesses in many of its subsequences. [1] R. Wilber, "Lower Bounds for Accessing Binary Search Trees With Rotations" SIAM J. Computing, 18(1) (1989) pp. 56-67. [2] R. Tarjan, "Sequential Access in Splay Trees Takes Linear Time", Combinatorica 5 (1985) pp. 367-378.

From:rew@lightstone.com (Bob Wilber at PUMICE)Newsgroups:comp.theorySubject:Re[2]: Jordan Sequences for which Splay Sort is n log nDate:1 Oct 1995 13:28:32 -0500Organization:UTexas Mail-to-News Gateway

There is a statement I made in my last post that needs some correction and clarification. Paul Callahan said: >In the following, I'm going to use the claim that sorting a sequence by >inserting it into a binary tree is as hard as accessing the same >sequence in a tree containing these values. I haven't proved this, >but it seems to me that each time a value is inserted (a new leaf >added at what was a "null pointer"), one could imagine that that value >already existed as a node in the tree but had not previously been >accessed. It should thus be possible to construct an initial tree >containing the values to be sorted for which the rotation sequence is >the same whether one is inserting into an intially empty tree, or >accessing from an initally full tree. >(Originally, I had a more >complicated idea for a proof that would not require this claim >but I think it is true, and it results in a cleaner argument). and I said >I believe your claim is false... It is clear that the model of insertion that Callahan had in mind is that nodes are always inserted as leaves in the appropriate part of the tree. It that case his claim is easily proven to be true. Starting from an empty tree, carry out a sequence of rotations and insertions of new leaves until all nodes have been inserted, creating some tree T. Now carry out the sequence backward, starting from T, except that when you would delete a leaf (the backwards version of inserting it), instead leave the node in place and mark it as deleted. Subsequent rotations in the backwards sequence do not involve any marked leaves. Furthermore, leaves marked as deleted stay at the fringe of the tree, that is, it is never the case that a marked leaf has an unmarked leaf as a child. So the backward sequence of rotations can be carried out. In the final tree all nodes are marked. This is the tree that satisfies the claim. What I had in mind was a more general model of insertion, namely, the reverse of "standard deletions", and it is with this more general type of insertion that the claim appears to be false. A standard insertion of a node v into a tree T is defined as follows: 1. Let x be the largest node < v in T, and let y be the smallest node > v in T. (For now assume that v is neither smaller than every node in T, nor bigger than every node in T.) 2. Either x is an ancestor of y or y is an ancestor of x. Assume the former. Let u[0] = x, u[1], u[2], ..., u[k] = y be the path from x to y. u[1] is the right child of x and for i > 1, u[i] is the left child of u[i-1]. Node v can be made a child of any one of the u[i]s. If it is made a child of x, it is a right child, otherwise it is a left child. v has no left child and is given u[i+1] as a right child (unless i = k, in which case v is a leaf). 3. If v is less than every node in T, we can either make v the root (with T as its right subtree) or can insert v as a left child of any of the nodes along the leftmost path of T. Similarly when v is greater than every node in T. 4. The cost of a standard insertion is the cost of following the path from the root to v after v is inserted. Note that the argument used above to prove Callahan's claim for insertions of leaves doesn't work for the more general type of insertion, because marked nodes might be left in the middle of the tree (with unmarked nodes as children) and this can make subsequent rotations in the reverse sequence invalid. It is trivial to emulate a splay tree insertion by means of rotations and a standard insertion, with no change in the cost of the operation. I don't see any way to emulate a splay tree insertion with rotations and an insertion of a leaf, while retaining the original cost. So the "patched up" lower bound of my previous post seems to be necessary to be able to claim that a splay sort of a bit reversal permutation, or of a Jordan sequence, requires n log n time.

From:callahan@biffvm.cs.jhu.edu (Paul Callahan)Newsgroups:comp.theorySubject:Re: Re[2]: Jordan Sequences for which Splay Sort is n log nDate:2 Oct 1995 11:49:20 -0400Organization:The Johns Hopkins University CS Department

In article <06edc080@lightstone.com>, Bob Wilber at PUMICE <rew@lightstone.com> wrote: >There is a statement I made in my last post that needs some correction and >clarification. > ... >It is clear that the model of insertion that Callahan had in mind is that nodes >are always inserted as leaves in the appropriate part of the tree. It that >case his claim is easily proven to be true. ... >What I had in mind was a more general model of insertion, namely, the reverse >of "standard deletions", and it is with this more general type of insertion >that the claim appears to be false. OK, this is a point I hadn't considered, so I guess things are a bit more complicated than I had hoped. As I mentioned, I had a backup argument. This relied on a different claim that seemed clear at the time, namely that to insert an element into a binary tree, one must access either its successor or predecessor in symmetric order. Now that you bring up the issue of general insertions, even the latter claim seems less clear to me, because it is only true in the case of leaf insertions that one must link the node directly to either its successor or predecessor. However, it should still hold because one cannot certify that a node is being inserted into the correct place without having seen its successor and predecessor (at least assuming no extra information is maintained in the tree). Anyway, instead of bounding the rotations from the very beginning, we can simply ignore the cost of inserting the first half of the bit-reversed sequence (even-valued elements). Then, to bound the cost of inserting the remaining (odd-valued) elements, we would find the cost of accessing any sequence of successors or predecessors of these elements (which I think should be Omega(n log n)). Since the above poster seems to have patched up my argument to his own satisfaction, there is probably no need for this (especially if the correspondence between his name and the author of one of the cited papers is not coincidental.) Actually, this brings up another unstated assumption I would have to use, which is that the cost of accessing *any* subsequence of n/2 elements from a list of n elements in bit-reversed order is Omega(n log n). I would be surprised if this were not true, but I don't know the best way of proving it. Clearly, there are some sequences that are "hard" to access but which contain an "easy" subsequence of length n/2, but intuitively it looks like any subsequence of a bit-reversed permutation should have the same property of breaking down the kind of locality of reference needed to obtain o(n log n) rotations. I'd appreciate any insight into this. I suspect that the machinery needed for the lower bound on bit-reversed sequences would be sufficient, but maybe there is a simpler argument. -- --- Paul Callahan --- callahan@cs.jhu.edu --- "The first principle in science is to invent something nice to look at and then decide what it can do." -- Rowland Emett

From:rew@lightstone.com (Bob Wilber at PUMICE)Newsgroups:comp.theorySubject:Re: Jordan Sequences for which Splay Sort is n log nDate:3 Oct 1995 14:34:15 -0500Organization:UTexas Mail-to-News Gateway

I wrote: >What I had in mind was a more general model of insertion, namely, the reverse >of "standard deletions", and it is with this more general type of insertion >that the claim appears to be false. Paul Callahan wrote: >OK, this is a point I hadn't considered, so I guess things are a bit >more complicated than I had hoped. As I mentioned, I had a backup >argument. This relied on a different claim that seemed clear at the >time, namely that to insert an element into a binary tree, one must >access either its successor or predecessor in symmetric order. > >Now that you bring up the issue of general insertions, even the latter >claim seems less clear to me, because it is only true in the >case of leaf insertions that one must link the node directly to >either its successor or predecessor. However, it should still hold >because one cannot certify that a node is being inserted into the >correct place without having seen its successor and predecessor (at least >assuming no extra information is maintained in the tree). Well, this brings up an issue that arises with any sort of lower bound -- what's the right model? When inserting node v in a tree that contains immediate predecessor x and immediate successor y, it is arguable that one should charge for the cost of finding both x and y, in order to certify that v is being inserted in a legal spot (let's call these two nodes bounds(v)). Instead, for standard insertions I charge the cost of following the path from the root to the newly inserted node. My reasons for choosing the cost model I did are as follows: 1. Symmetry. The cost of a standard insertion is the same as the cost of a standard deletion of the same node in the time reversed sequence. It is clear that when deleting node v it is not necessary to charge for finding bounds(v). 2. Generality. This is a more generous cost model than the one that charges for finding bounds(v), so any lower bound obtained with this cost model will apply to a broader class of algorithms. In principle, an algorithm doesn't need to look for bounds(v). For example, store the minimum and maximum values in the entire tree, and in addition, store with each non-root node v the minimum value of the subtree it is a root of, if v is a right child of its parent, or the maximum value of the subtree it is a root of, if v is a left child of its parent. With these values we can verify the validity of an insertion while only having to look as far as the child of the node being inserted. These values can be maintained in constant time under rotations. For example, if x is a left child of z and y is a right child of x, then when x is rotated over z, x gets z's old extremum value (either a minimum or a maximum), z gets y's old minimum, and y gets x's old maximum. When a standard deletion or insertion is done, the cost of making the required updates of extrema can be charged against the cost of following the path from the root to the inserted or deleted node. Most balanced search tree algorithms need *some* sort of extra information in the tree. For example, red-black trees need a bit per node that tells whether they're red or black (splay trees are unusual in that they don't have any such extra information). So, while storing one extra value in each node is more overhead than some other search algorithms have, it seems arbitrary to reject out of hand algorithms that do that. And there might be a less costly way to avoid looking at bounds(v). 3. Simplicity. If I charge for finding bounds(v), I have to figure out what bounds(v) is. For a highly regular sequence like the bit reversal permutation this is easy, but in general it might be harder than counting end accesses. >Anyway, instead of bounding the rotations from the very beginning, we >can simply ignore the cost of inserting the first half of the >bit-reversed sequence (even-valued elements). Then, to bound the cost >of inserting the remaining (odd-valued) elements, we would find the >cost of accessing any sequence of successors or predecessors of these >elements (which I think should be Omega(n log n)). Well, yes, if for inserting each node v you charge for accessing bounds(v) I believe this works. For the second half of the bit reversal permutation, br(n/2), br(n/2 + 1), ..., br(n-1), the nodes accessed are bounds(br(n/2)), bounds(br(n/2 + 1)), ..., bounds(br(n-1)), from which we can extract the subsequence br(0), br(1), ..., br(n/2 - 1). And this takes Omega(n log n) time to access. A complicating factor is that as you proceed, nodes are being inserted into the tree (you're not just doing accesses) but I don't think this affects the validity of the lower bound proofs. This is sufficient to establish a bound on splay sorting, since a splay insertion of v does in fact access bounds(v). >Since the above poster seems to have patched up my argument to his own >satisfaction, there is probably no need for this (especially if the >correspondence between his name and the author of one of the cited papers is >not coincidental.) The probability of two people with my name looking at this problem is low. >Actually, this brings up another unstated assumption I would have to >use, which is that the cost of accessing *any* subsequence of n/2 >elements from a list of n elements in bit-reversed order is >Omega(n log n). I would be surprised if this were not true, but I don't know >the best way of proving it. I thought this was self evident. Suppose I can access some sequence s[1], s[2], ..., s[n] in time f(n). Then the same algorithm also accesses any subsequence, s[i_1], s[i_2], ..., s[i_k] in time f(n). (Just ignore the accesses you don't care about.) So any lower bound on accessing the subsequence is necessarily a lower bound on accessing the full sequence.

From:callahan@condor.cs.jhu.edu (Paul Callahan)Newsgroups:comp.theorySubject:Re: Jordan Sequences for which Splay Sort is n log nDate:3 Oct 1995 17:23:32 -0400Organization:The Johns Hopkins University CS Department

In article <0718e6e0@lightstone.com>, Bob Wilber at PUMICE <rew@lightstone.com> wrote: >I thought this was self evident. Suppose I can access some sequence s[1], >s[2], ..., s[n] in time f(n). Then the same algorithm also accesses any >subsequence, s[i_1], s[i_2], ..., s[i_k] in time f(n). (Just ignore the >accesses you don't care about.) So any lower bound on accessing the >subsequence is necessarily a lower bound on accessing the full sequence. Actually, I meant that the bound should also hold in the other direction for bit-reversed sequences. What I want to show is that the lower bound for the full bit-reversed sequence is (to within a constant) a lower bound for any subsequence containing half the elements. There are sequences for which this doesn't hold. For example, interleave a bit-reversed sequence with a sequence in increasing order. Then the full sequence requires Omega(n log n) rotations for access, but it contains a subsequence (the one in increasing order) that requires O(n) rotations. But what I'm claiming is that the bit-reversed sequence does not contain any such "easy" sequence as a subsequence. Is this true? -- --- Paul Callahan --- callahan@cs.jhu.edu --- "The first principle in science is to invent something nice to look at and then decide what it can do." -- Rowland Emett

From:rew@lightstone.com (Bob Wilber at PUMICE)Newsgroups:comp.theorySubject:Re: Jordan Sequences for which Splay Sort is n log nDate:4 Oct 1995 11:59:49 -0500Organization:UTexas Mail-to-News Gateway

>Actually, I meant that the bound should also hold in the other >direction for bit-reversed sequences. What I want to show is that the >lower bound for the full bit-reversed sequence is (to within a >constant) a lower bound for any subsequence containing half the >elements. > >There are sequences for which this doesn't hold. For example, interleave >a bit-reversed sequence with a sequence in increasing order. Then >the full sequence requires Omega(n log n) rotations for access, but >it contains a subsequence (the one in increasing order) that requires >O(n) rotations. But what I'm claiming is that the bit-reversed >sequence does not contain any such "easy" sequence as a subsequence. > >I this true? I suspect that it is, but I don't have a proof. However, you don't need such a strong claim for your proof to work. Let's look at it again. We have a proof that accessing a bit reversal permutation of length n via a binary search tree algorithm requires c * n log n time, for some c > 0. We insert into an initially empty tree a bit reversal permutation on k bits, k with n = 2 elements. We want to show that inserting the last n/2 elements requires accessing the n/2 nodes already in tree in bit reversal order. Fix k at 4. When br(n/2) = 0001 is inserted, we must access the lower of bounds(0001), namely, the lower of 0000 and 0010. The higher of these two nodes is an ancestor of the lower, so we actually visit both and are free to charge for accessing either one. So charge for acessing 0000. When we insert br(n/2 + 1) = 1001, we must access 1000 and 1010. Charge for 1000. When we insert br(n/2 + 1) = 0101, we must access 0100 and 0110. Charge for 0100. The sequence of accesses we charge for, 0000, 1000, 0100, 1100, ...., 1110, is a full bit reversal permutation on k-1 bits (the k'th bit being fixed at 0), with no missing elements. So this takes c*(n/2) log (n/2) = Omega(n log n) time. The only lower bound being applied here is to a complete bit reversal permutation, not some arbitrary subsequence of a bit reversal permutation.