✦ LIBER ✦

A tight lower bound for top-down skew heaps

✍ Scribed by Berry Schoenmakers

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 498 KB
Volume: 61
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00028-8

No coin nor oath required. For personal study only.

✦ Synopsis

Previously, it was shown in a paper by Kaldewaij and Schoenmakers that for top-down skew heaps the amortized number of comparisons required for meld and delmin is upper bounded by log+ R, where n is the total size of the inputs to these operations and r#~ = (& + 1) /2 denotes the golden ratio. In this paper we present worst-case sequences of operations on top-down skew heaps in which each application of meld and delmin requires approximately log4 n comparisons. As the remaining heap operations require no comparisons, it then follows that the set of bounds is tight. The result relies on a particular class of self-recreating binary trees, which is related to a sequence known as Hofstadter's G-sequence. @

📜 SIMILAR VOLUMES

The derivation of a tighter bound for to

The derivation of a tighter bound for top-down skew heaps

✍ Anne Kaldewaij; Berry Schoenmakers 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 915 KB

A tight lower bound for the train revers

A tight lower bound for the train reversal problem

✍ Alok Aggarwal; Tom Leighton 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 319 KB

A tight lower bound for the completion t

A tight lower bound for the completion time variance problem

✍ C.T. Ng; X. Cai; T.C.E. Cheng 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 216 KB

A tight lower bound for the Steiner rati

A tight lower bound for the Steiner ratio in Minkowski planes

✍ Biao Gao; Ding-Zhu Du; Ronald L. Graham 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 804 KB

A minimum Steiner tree for a given set X of points is a network interconnecting the points of X having minimum possible total length. The Steiner ratio for a metric space is the largest lower bound for the ratio of lengths between a minimum Steiner tree and a minimum spanning tree on the same set of

Lower convex order bound approximations

Lower convex order bound approximations for sums of log-skew normal random variables

✍ Oriol Roch; Emiliano A. Valdez 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 241 KB

When it comes to modeling dependent random variables, not surprisingly, the multivariate normal distribution has received the most attention because of its many appealing properties. However, when it comes to practical implementation, the same family of distribution is often rejected for modeling fi