Name
Abstract | ||
|---|---|---|
. We investigate the distribution of the number of comparisons made by MULTIPLE QUICK SELECT (a variant of QUICK SORT for finding
order statistics). By convergence in the Wasserstein metric space, we show that a limit distribution exists for a suitably
normalized version of the number of comparisons. We characterize the limiting distribution by an inductive convolution and
find its variance. We show that the limiting distribution is smooth and prove that it has a continuous density with unbounded
support. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/PL00009241 | Algorithmica |
Keywords | Field | DocType |
Key words. Sorting,Limit distribution. | Applied mathematics,Discrete mathematics,Random variable,Mathematical optimization,Convolution,Probabilistic analysis of algorithms,Smoothing,Wasserstein metric,Metric space,Order statistic,Mathematics,Asymptotic distribution | Journal |
Volume | Issue | ISSN |
22 | 4 | 0178-4617 |
Citations | PageRank | References |
7 | 0.74 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hosam M. Mahmoud | 1 | 183 | 55.63 |
| Robert T. Smythe | 2 | 92 | 39.96 |