Abstract
Basic methods are given to evaluate or estimate the median for various probability distributions. These methods are then applied to determine the precise median of several nontrivial distributions, including weighted selection and the sum of heterogeneous Bernoulli trials conditioned to lie within any interval centered about the mean. These bounds are then used to give simple analyses of algorithms such as interpolation search and some aspects of PRAM emulation.
Original language | English (US) |
---|---|
Pages (from-to) | 184-236 |
Number of pages | 53 |
Journal | Journal of Algorithms |
Volume | 38 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2001 |
Keywords
- Bernoulli trials
- Conditioned Bernoulli trials
- Conditioned hypergeometric distribution
- Hypergeometric distribution
- Interpolation search
- Median
- PRAM emulation
- Weighted selection
ASJC Scopus subject areas
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics