✦ LIBER ✦

A tradeoff between search and update in dictionaries

✍ Scribed by Jaikumar Radhakrishnan; Venkatesh Raman

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 64 KB
Volume: 80
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(01)00173-9

No coin nor oath required. For personal study only.

✦ Synopsis

Borodin, Fich, Meyer auf der Heide, Upfal and Wigderson [Theoret. Comput. Sci. 58 (1998) 57-68] showed lower bounds for search time in implicit dictionaries with bounded update time. In particular, their result implies a lower bound of (n ε ) for search time in an implicit dictionary whenever the update time is bounded by a constant. They ask whether a similar result is true for dictionaries with explicit pointers. We answer their question in the affirmative by observing that stronger results follow easily from an earlier result of Borodin, Guibas, Lynch and Yao [Inform. Process. Lett. 12 (1981) 71-75]. In particular, a lower bound of (n) for search time holds whenever the update time is bounded by a constant. Our results hold even if the dictionary uses randomization and the update time is amortized.

📜 SIMILAR VOLUMES

A tradeoff between search and update tim

A tradeoff between search and update time for the implicit dictionary problem

✍ Allan Borodin; Faith E. Fich; Friedhelm Meyer Auf Der Heide; Eli Upfal; Avi Wigd 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 698 KB

Quantifying tradeoffs between costs and

Quantifying tradeoffs between costs and prices in utility DSM programs

✍ Eric Hirst 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 664 KB

Tradeoffs between oxygen and energy in t

Tradeoffs between oxygen and energy in tibial growth at high altitude

✍ S.M. Bailey; J. Xu; J.H. Feng; X. Hu; C. Zhang; S. Qui 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

Tradeoff between height and relative gro

Tradeoff between height and relative growth rate in a dominant grass from the Serengeti ecosystem

✍ G. Hartvigsen; S. J. McNaughton 📂 Article 📅 1995 🏛 Springer-Verlag 🌐 English ⚖ 373 KB

We determined the relationship between plant height and whole-plant relative growth rate (g g day) for ten genotypes of Sporobolus kentrophyllus collected from an intensively grazed site on the Serengeti Plains, Tanzania. Plants were grown for 7 weeks in a greenhouse in Syracuse, N.Y., and harvested

On the tradeoff between the law of large

On the tradeoff between the law of large numbers and oligopoly in insurance

✍ Michael R. Powers; Martin Shubik 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 856 KB

For a fixed number of customers in an insurance market, changing the number of insurance firms creates both scale effects on the individual firms (as the number of customers per firm is altered), and an oligopolistic effect on market supply. The most prominent effect of scale is the impact on solven

Tradeoffs Between Ideas and Structure: I

Tradeoffs Between Ideas and Structure: Individual Versus Group Performance in Creative Problem Solving

✍ Dr. MICHAEL D. MUMFORD; JACK M. FELDMAN; MICHAEL B. HEIN; DENNIS J. NAGAO 📂 Article 📅 2001 🏛 Creative Education Foundation 🌐 English ⚖ 115 KB

## Abstract The present effort was intended to assess how situational variables influence the relative performance of groups and individuals on creative problem‐solving tasks. More specifically, a priming manipulation was used to increase the number of alternatives available for problem solving whi