𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A probabilistic analysis of the height of tries and of the complexity of triesort

✍ Scribed by Luc Devroye

Publisher
Springer-Verlag
Year
1984
Tongue
English
Weight
313 KB
Volume
21
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Probabilistic analysis of the complexity
Probabilistic analysis of the complexity of Aβˆ—
✍ Nam Huyn; Rina Dechter; Judea Pearl πŸ“‚ Article πŸ“… 1980 πŸ› Elsevier Science 🌐 English βš– 598 KB

## This paper analyzes the number of nodes expanded by A* as a function of the accuracy of its heuristic estimates by treating the errors h * -h as random variables whose distributions may vary over the nodes in the graph. Our model consists of an m -ary tree with unit branch costs and a unique goal

Probabilistic analysis of the time compl
Probabilistic analysis of the time complexity of quicksort
✍ Tadashi Mizoi; Shunji Osaki πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 460 KB

## Abstract Quicksort is a well‐known sorting algorithm based on the divided control. the array to be sorted is divided into two sets as follows. an element in the array is specified, and the set of values larger than the value of that element and the set of values smaller than that value are const

Complexity analysis of the SAT engine: D
Complexity analysis of the SAT engine: DNA algorithms as probabilistic algorithms
✍ Masami Hagiya; John A. Rose; Ken Komiya; Kensaku Sakamoto πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 123 KB

Taking advantage of the power of DNA molecules to spontaneously form hairpin structures, Sakamoto et al. designed a molecular algorithm to solve instances of the satisΓΏability problem on Boolean expressions in clausal form (the SAT problem), and by developing new experimental techniques for molecula

A probabilistic upper bound for the edge
A probabilistic upper bound for the edge identification complexity of graphs
✍ Eberhard Triesch πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 344 KB

Given a finite graph G=( V, E), what is the minimum number c(G) of incidence tests which are needed in the worst case to identify an unknown edge e\*EE? The number c(G) was first studied by Aigner and Triesch (1988), where it was shown that for almost all graphs in the random graph model where d(n)

On the complexity of inference about pro
On the complexity of inference about probabilistic relational models
✍ Manfred Jaeger πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 120 KB

We investigate the complexity of probabilistic inference from knowledge bases that encode probability distributions on finite domain relational structures. Our interest here lies in the complexity in terms of the domain under consideration in a specific application instance. We obtain the result tha