Searching for losers
- 1 January 1993
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 4 (1) , 99-110
- https://doi.org/10.1002/rsa.3240040107
Abstract
We investigate the following process: N people select b losers by flipping coins. The 0‐party continues until there are less than b losers; then the 1‐party has to find the other losers by the same process. The average time for this process is about long2 N, but this result requires rather advanced methods. Furthermore, the average size of a binary tree associated to this process and the average number of coin flippings are computed. The method used in this article can be used to give asympotical solutions of a special type of bivariate recurrences. © 1993 John Wiley & Sons, Inc.Keywords
This publication has 5 references indexed in Scilit:
- Patricia tries again revisitedJournal of the ACM, 1990
- Singularity Analysis of Generating FunctionsSIAM Journal on Discrete Mathematics, 1990
- Solution of a Linear Recurrence Equation Arising in the Analysis of Some AlgorithmsSIAM Journal on Algebraic Discrete Methods, 1987
- The complexity of generating an exponentially distributed variateJournal of Algorithms, 1986
- Handbuch der Laplace-TransformationPublished by Springer Nature ,1950