An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms

Adams, 1974 Albacea, 1995, Leapfrogging samplesort, 1023, 1 Andersson, 1999, General balanced trees, J. Algorithms, 30, 1, 10.1006/jagm.1998.0967 Ashcraft, 1999, SPOOLES: an object-oriented sparse matrix library, 10 Baer, 1989, Improving quicksort performance with a codeword data structure, IEEE Trans. Software Engrg., 15, 622, 10.1109/32.24711 Baeza-Yates, 1987, Some average measures in m-ary search trees, Inform. Process. Lett., 25, 375, 10.1016/0020-0190(87)90215-8 Baeza-Yates, 1991, Height balance distribution of search trees, Inform. Process. Lett., 39, 317, 10.1016/0020-0190(91)90005-3 Battiato, 2000, An efficient algorithm for the approximate median selection problem, 1767, 226 Bender, 1999 Bentley, 1993, Engineering a sort function, Software–Pract. Exper., 23, 1249, 10.1002/spe.4380231105 Bentley, 1997, Fast algorithms for sorting and searching strings, 360 Bergeron, 1992, Varieties of increasing trees, 581, 24 Billingsley, 1995 Burge, 1972, Analysis of a tree sorting method and some properties of a set of trees, 372 Chao, 1993, The asymptotic distributions of the remedians, J. Statist. Plann. Inference, 37, 1, 10.1016/0378-3758(93)90075-H Chebyshev, 1962, II W.-M. Chen, H.-K. Hwang, Analysis of two randomized algorithms for finding the maximum in a broadcast communication model, submitted, 2001; available via http://algo.stat.sinica.edu.tw Chern, 2001, Transitional behaviors of the average cost of quicksort with median-of-(2t+1), Algorithmica, 29, 44, 10.1007/BF02679613 Chern, 2001, Phase changes in random m-ary search trees and generalized quicksort, Random Structures Algorithms, 19, 316, 10.1002/rsa.10005 Chern, 2000, Distribution of the number of consecutive records, Random Structures Algorithms, 17, 169, 10.1002/1098-2418(200010/12)17:3/4<169::AID-RSA1>3.0.CO;2-K Comtet, 1974 Cook, 1980, Best sorting algorithms for nearly sorted lists, Comm. ACM, 23, 620, 10.1145/359024.359026 Cormen, 1990 Cox, 1992, The ninther and its relatives: summary measures useful in geomorphology, Z. Geomorph., 36, 491, 10.1127/zfg/36/1992/491 Cunto, 1987, Improving time and space efficiency in generalized binary search trees, Acta Inform., 24, 583, 10.1007/BF00263296 Delange, 1991, On the use of the method of moments for the study of additive functions, J. Number Theory, 39, 144, 10.1016/0022-314X(91)90041-9 Devroye, 1983, Moment inequalities for random variables in computational geometry, Computing, 30, 111, 10.1007/BF02280782 Devroye, 1999, Universal limit laws for depths in random trees, SIAM J. Comput., 28, 409, 10.1137/S0097539795283954 Devroye, 2002, Limit laws for sums of functions of subtrees of random binary search trees, SIAM J. Comput., 10.1137/S0097539701383923 Devroye, 2000, Perfect simulation from the quicksort limit distribution, Electron. Comm. Probab., 5, 95, 10.1214/ECP.v5-1024 Diaconis, 1987, Application of the method of moments in probability and statistics, 125 Dionisi, 1999, Supercritical CO2 extraction for total fat analysis of food products, J. Food Sci., 64, 612, 10.1111/j.1365-2621.1999.tb15095.x Dromey, 1984, Exploiting partial order with quicksort, Software—Pract. Exp., 14, 509, 10.1002/spe.4380140603 2001, Theoret. Comput. Sci., 265 M. Durand, Holonomie et applications en l'analyse d'algorithmes et combinatoire, DEA Mémoire, LIX, École Polytechnique, 2000; available via http://algo.inria.fr/durand Durian, 1986, Quicksort without a stack, 233, 283 Fill, 1996, On the distribution of binary search trees under the random permutation model, Random Structures Algorithms, 8, 1, 10.1002/(SICI)1098-2418(199601)8:1<1::AID-RSA1>3.0.CO;2-1 J.A. Fill, Transfer theorems and asymptotic distributional results for m-ary search trees, manuscript, 2001 J.A. Fill, S. Janson, Quicksort asymptotics, preprint, 2001; available via http://www.mts.jhu.edu/~fill Flajolet, 1993, Analytic variations on quadtrees, Algorithmica, 10, 473, 10.1007/BF01891833 Flajolet, 1982, The average height of binary trees and other simple trees, J. Comput. System Sci., 25, 171, 10.1016/0022-0000(82)90004-6 Flajolet, 1990, Singularity analysis of generating functions, SIAM J. Discrete Math., 3, 216, 10.1137/0403019 Flajolet, 1998, On the analysis of linear probing hashing, Algorithmica, 22, 490, 10.1007/PL00009236 Flajolet, 1986, Partial match retrieval of multidimensional data, J. ACM, 33, 371, 10.1145/5383.5453 Françon, 1976, Arbres binaires de recherche: propriétés combinatoires et application, RAIRO Inform. Théor., 10, 35 Fréchet, 1931, A proof of the generalized second-limit theorem in the theory of probability, Trans. Amer. Math. Soc., 33, 533, 10.2307/1989421 Gonnet, 1991 Grabner, 2001, Sorting algorithms for broadcast communications: Mathematical analysis, Theoret. Comput. Sci. D.H. Greene, Labelled Formal Languages and Their Uses, PhD thesis, Stanford University, 1983 Hammersley, 1962, Generalization of the fundamental theorem on sub-additive functions, Proc. Cambridge Philos. Soc., 58, 235, 10.1017/S030500410003646X Hammersley, 1974, Maximal solutions of the generalized subadditive inequality, 270 Hennequin, 1989, Combinatorial analysis of quicksort algorithm, RAIRO Inform. Théor. Appl., 23, 317, 10.1051/ita/1989230303171 P. Hennequin, Analyse en moyenne d'algorithme, tri rapide et arbres de recherche, PhD thesis, École Polytechnique, 1991 Hille, 1959, I Hoare, 1961, Algorithm 64: Quicksort, Comm. ACM, 4, 321, 10.1145/366622.366644 Hoare, 1962, Quicksort, Comput. J., 5, 10, 10.1093/comjnl/5.1.10 Huang, 1986, A one-way, stackless quicksort algorithm, BIT, 26, 127, 10.1007/BF01939369 Hubalek, 2002, A multivariate view of random bucket digital search trees, J. Algorithms, 44, 121, 10.1016/S0196-6774(02)00210-9 Hurley, 1995, Low-storage quantile estimation, Comput. Statist., 10, 311 Hwang, 2002, Second phase changes in random m-ary search trees and generalized quicksort, Ann. Probab. Hwang, 2002, Phase changes of the limit laws in the quicksort recurrence under varying toll functions, SIAM J. Comput., 10.1137/S009753970138390X Hwang, 2002, Quickselect and Dickman function, Combin. Probab. Comput., 10.1017/S0963548302005138 H.-K. Hwang, T.-H. Tsai, An asymptotic theory for recurrence relations based on minimization and maximization, submitted, 2001; available via http://algo.stat.sinica.edu.tw Ince, 1926 JaJa, 2000, A perspective on quicksort, Comput. Sci. Engrg., 43, 10.1109/5992.814657 Janson, 2000 Kaykobad, 1998, 3 is a more promising algorithmic parameter than 2, Comput. Math. Appl., 36, 19, 10.1016/S0898-1221(98)00158-8 Kersten, 1999, Fuzzy order statistics and their applications to fuzzy clustering, IEEE Trans. Fuzzy Systems, 7, 708, 10.1109/91.811239 Kirschenhofer, 1997, Analysis of Hoare's FIND algorithm with median-of-three partition, Random Structures Algorithms, 10, 143, 10.1002/(SICI)1098-2418(199701/03)10:1/2<143::AID-RSA7>3.0.CO;2-V Knessl, 1999, Quicksort algorithm again revisited, Discrete Math. Theor. Comput. Sci., 3, 43 Knuth, 1998, III Kundu, 1977, Sorting tree, nestling tree and inverse permutation, Inform. Process. Lett., 6, 94, 10.1016/0020-0190(77)90035-7 J.N. Larsson, K. Sadakane, Faster suffix sorting, Technical Report, LU-CS-TR:99-214, LUNDFD6/(NFCS-3140)/1–20/(1999), Department of Computer Science, Lund University; available via http://www.cs.lth.se/~jesper/ssrev-tr.pdf Lew, 1994, The joint distribution of elastic buckets in multiway search trees, SIAM J. Comput., 23, 1050, 10.1137/S009753979223023X Loève, 1977, 45 Mahmoud, 1992 Mahmoud, 1998, On rotations in fringe-balanced binary trees, Inform. Process. Lett., 65, 41, 10.1016/S0020-0190(97)00184-1 H.M. Mahmoud, The size of random bucket trees via urn models, manuscript, 2001 Mahmoud, 1989, Analysis of the space of search trees under the random insertion algorithm, J. Algorithms, 10, 52, 10.1016/0196-6774(89)90023-0 Mahmoud, 1995, Probabilistic analysis of bucket recursive trees, Theoret. Comput. Sci., 144, 221, 10.1016/0304-3975(94)00308-6 Manku, 1998, Approximate medians and other quantiles in one pass and with limited memory, 27, 426 Martı&#x0301;nez, 2001, Optimal sampling strategies in quicksort and quickselect, SIAM J. Comput., 31, 683, 10.1137/S0097539700382108 McDiarmid, 1996, Large deviations for quicksort, J. Algorithms, 21, 476, 10.1006/jagm.1996.0055 Moffat, 1995, In-place calculation of minimum-redundancy codes, 393 Motzkin, 1981, A stable quicksort, Software–Pract. Exp., 11, 607, 10.1002/spe.4380110604 Musser, 1997, Introspective sorting and selection algorithms, Software–Pract. Exp., 27, 983, 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# Nagle, 2000 R. Neininger, L. Rüschendorf, A general contraction theorem and asymptotic normality in combinatorial structures, preprint, 2001; available via http://www.stochastik.uni-freiburg.de/homepages/neininger Panholzer, 1998, An analytic approach for the analysis of rotations in fringe-balanced binary search trees, Ann. Comb., 2, 173, 10.1007/BF01608487 Pearl, 1981, A space-efficient on-line method of computing quantile estimates, J. Algorithms, 2, 164, 10.1016/0196-6774(81)90017-1 Pittel, 1999, Normal convergence problem? Two moments and a recurrence may be the clues, Ann. Appl. Probab., 9, 1260, 10.1214/aoap/1029962872 Poblete, 1993, The analysis of heuristics for search trees, Acta Inform., 30, 233, 10.1007/BF01179372 Poblete, 1985, The analysis of a fringe heuristic for binary search trees, J. Algorithms, 6, 336, 10.1016/0196-6774(85)90003-3 Prodinger, 1996, Depth and path length of heap ordered trees, Int. J. Found. Comput. Sci., 7, 293, 10.1142/S0129054196000208 Röhrich, 1982, A hybrid of quicksort with O(nlogn) worst case complexity, Inform. Process. Lett., 14, 119, 10.1016/0020-0190(82)90067-9 Rösler, 2001, The contraction method for recursive algorithms, Algorithmica, 29, 3, 10.1007/BF02679611 Rousseeuw, 1990, The remedian: A robust averaging method for large data sets, J. Amer. Statist. Assoc., 85, 97, 10.2307/2289530 Sarwar, 1996, Engineering quicksort, Comput. Lang., 22, 39, 10.1016/0096-0551(96)00005-7 Schachinger, 2000, Limiting distribution of the costs of partial match retrievals in multidimensional tries, Random Structures Algorithms, 17, 428, 10.1002/1098-2418(200010/12)17:3/4<428::AID-RSA12>3.0.CO;2-6 Sedgewick, 1977, Quicksort with equal keys, SIAM J. Comput., 6, 240, 10.1137/0206018 Sedgewick, 1980 Shiau, 1999, A fast sorting algorithm on broadcast communications, 87 W.D. Smith, Fixed point for negamaxing probability distributions on regular trees, preprint, 1995, available via http://citeseer.nj.nec.com/67965.html Smythe, 1996, Central limit theorems for urn models, Stochastic Process. Appl., 65, 115, 10.1016/S0304-4149(96)00094-4 Smythe, 1996, A survey of recursive trees, Theory Probab. Math. Statist., 51, 1 Stanley, 1997, 1 Stephenson, 1980, A method of constructing binary search trees by making insertions at the root, Int. J. Comput. Inform. Sci., 9, 15, 10.1007/BF00995807 Szwarcfiter, 1978, Some properties of ternary trees, Comput. J., 21, 66, 10.1093/comjnl/21.1.66 Takács, 1994, On the total heights of random rooted binary trees, J. Comb. Theory Ser. B, 61, 155, 10.1006/jctb.1994.1041 K.-H. Tan, An Asymptotic Analysis of the Number of Comparisons in Multipartition Quicksort, PhD dissertation, Carnegie-Mellon University, 1993 Tukey, 1978, The ninther, a technique for low-effort robust (resistant) location in large samples, 251 Valois, 2000, Introspective sorting and selection revisited, Software–Pract. Exp., 30, 617, 10.1002/(SICI)1097-024X(200005)30:6<617::AID-SPE311>3.0.CO;2-A Vuillemin, 1980, A unifying look at data structures, Comm. ACM, 23, 229, 10.1145/358841.358852 Wainwright, 1984, A class of sorting algorithms based on quicksort, Comm. ACM, 28, 396, 10.1145/3341.3348 Wegner, 1985, Quicksort for equal keys, IEEE Trans. Comput., 34, 362, 10.1109/TC.1985.5009387 Wegner, 1987, A generalized, one-way, stackless quicksort, BIT, 27, 44, 10.1007/BF01937353 B.W. Weide, Statistical Methods in Algorithm Design and Analysis, PhD dissertation, Carnegie-Mellon University, 1978