Two methods are given for obtaining lower bounds on the cost of accessing a sequence of nodes in a symmetrically ordered binary search tree, in a model where rotations can be done on the tree and the entire sequence is known before accessing begins (but the accesses must be done in the order given). For example, it can be proven that the bit-reversal permutation requires $\Theta (n\log n)$ time to access in this model. It is also shown that the expected cost of accessing random sequences in this model is the same as it is for the case where the tree is static.

Article Free Access Share on Geometric applications of a matrix searching algorithm Authors: A Aggarwal IBM T. J. Watson Center, Yorktown Heights IBM T. J. Watson Center, Yorktown HeightsSearch about this author , M Klawe IBM Almaden Research Center, San Jose IBM Almaden Research Center, San JoseView Profile , S Moran IBM T. J. Watson Center, Yorktown Heights IBM T. J. Watson Center, Yorktown HeightsSearch about this author , P Shor Math. Sciences Research Institute, Berkeley Math. Sciences Research Institute, BerkeleyView Profile , R Wilber IBM Almaden Research Center, San Jose IBM Almaden Research Center, San JoseView Profile Authors Info & Claims SCG '86: Proceedings of the second annual symposium on Computational geometryAugust 1986Pages 285–292https://doi.org/10.1145/10515.10546Published:01 August 1986Publication History 39citation1,255DownloadsMetricsTotal Citations39Total Downloads1,255Last 12 Months234Last 6 weeks35 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We describe two methods for obtaining lower bounds on the cost of accessing a sequence of nodes of a symmetrically ordered binary search tree, where rotations can be done on the tree. The bounds apply to offline as well as online algorithms.

A family of directed acyclic graphs of vertex indegree 2 is constructed for which there are strategies of the black-white pebble game that use asymptotically fewer pebbles than the best strategies of the black pebble game. This shows that there are straight-line programs that can be evaluated nondeterministically with asymptotically less space than is required by any deterministic evaluation.

A language L is random with respect to a given complexity class C if for all ′ ∈ C L and ′ disagree on half of all strings. It is known that for any complexity class there are recursive languages that are random with respect to that class. Here it is shown that there are tight space and time hierarchies of random languages, and that EXPTIME contains P-isomorphism classes containing only languages that are random with respect to polynomial-time computations. The technique used is extended to show that for any constructible bound on time or space it is possible to deterministically generate binary sequences that appear random to all prediction algorithms subject to the given resource bound. Furthermore, the generation of such a sequence requires only slightly more resources than the given bound.