DATA-STRUCTURES MAXIMA

Authors
LOUCHARD G KENYON C SCHOTT R
Citation
G. Louchard et al., DATA-STRUCTURES MAXIMA, SIAM journal on computing, 26(4), 1997, pp. 1006-1042
Citations number
53
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
26
Issue
4
Year of publication
1997
Pages
1006 - 1042
Database
ISI
SICI code
0097-5397(1997)26:4<1006:DM>2.0.ZU;2-4
Abstract
The purpose of this paper is to analyze the maxima properties (value a nd position) of some data structures. Our theorems concern the distrib ution of these random variables. Previously known results usually deal t with the mean and sometimes the variance of the random variables. Ma ny of our results rely on diffusion techniques. This is a very powerfu l tool that has already been used with some success in algorithm compl exity analysis.