{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T09:06:34Z","timestamp":1776071194805,"version":"3.50.1"},"reference-count":57,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3850,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,1]]},"DOI":"10.1016\/s0304-3975(02)00066-x","type":"journal-article","created":{"date-parts":[[2003,2,5]],"date-time":"2003-02-05T01:51:53Z","timestamp":1044409913000},"page":"1475-1501","source":"Crossref","is-referenced-by-count":12,"title":["An asymptotic theory for recurrence relations based on minimization and maximization"],"prefix":"10.1016","volume":"290","author":[{"given":"Hsien-Kuei","family":"Hwang","sequence":"first","affiliation":[]},{"given":"Tsung-Hsi","family":"Tsai","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(02)00066-X_BIB1","series-title":"The Design and Analysis of Computer Algorithms, Second Printing","author":"Aho","year":"1975"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB2","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1137\/S0895480192232862","article-title":"Multidimensional divide-and-conquer maximin recurrences","volume":"8","author":"Alonso","year":"1995","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB3","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1137\/0603038","article-title":"Some maximal solutions of the generalized subadditive inequality","volume":"3","author":"Batty","year":"1982","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB4","series-title":"Regular Variation","author":"Bingham","year":"1989"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB5","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/S1385-7258(52)50021-0","article-title":"Some linear and some quadratic recursion formulas. II","volume":"14","author":"de Bruijn","year":"1952","journal-title":"Indagationes Mathematicae"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB6","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1215\/S0012-7094-71-03869-5","article-title":"A sorting function","volume":"38","author":"Carlitz","year":"1971","journal-title":"Duke Math. J."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB7","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01516009","article-title":"Huffman algebras for independent random variables","volume":"4","author":"Chang","year":"1994","journal-title":"Discrete Events Dynamic Systems"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB8","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1006\/jagm.1998.0986","article-title":"The cost distribution of queue-mergesort, optimal mergesorts, and power-of-2rules","volume":"30","author":"Chen","year":"1999","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB9","series-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB10","first-page":"31","article-title":"Sur la fonction sommatoire de la fonction somme des chiffres","volume":"21","author":"Delange","year":"1975","journal-title":"Enseign. Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB11","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02280782","article-title":"Moment inequalities for random variables in computational geometry","volume":"30","author":"Devroye","year":"1983","journal-title":"Computing"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199601)8:1<1::AID-RSA1>3.0.CO;2-1","article-title":"On the distribution of binary search trees under the random permutation model","volume":"8","author":"Fill","year":"1996","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB13","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1007\/BF01177551","article-title":"Mellin transforms and asymptotics","volume":"31","author":"Flajolet","year":"1994","journal-title":"Acta Inform."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB14","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(92)00065-Y","article-title":"Mellin transforms and asymptotics","volume":"123","author":"Flajolet","year":"1994","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(94)90226-7","article-title":"A calculus for the random generation of labelled combinatorial structures","volume":"132","author":"Flajolet","year":"1994","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB16","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1016\/0022-247X(74)90176-0","article-title":"Recurrence relations based on minimization","volume":"48","author":"Fredman","year":"1974","journal-title":"J. Math. Anal. Appl."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB17","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0127054","article-title":"A discrete search game","volume":"27","author":"Gal","year":"1974","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB18","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1137\/0131030","article-title":"On the optimality of Huffman trees","volume":"31","author":"Glassey","year":"1976","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB19","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0020-0190(93)90088-Q","article-title":"Queue-mergesort","volume":"48","author":"Golin","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB20","series-title":"Mathematics for the Analysis of Algorithms","author":"Greene","year":"1990"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB21","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1017\/S030500410003646X","article-title":"Generalization of the fundamental theorem on sub-additive functions","volume":"58","author":"Hammersley","year":"1962","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB22","series-title":"Stochastic Geometry","first-page":"270","article-title":"Maximal solutions of the generalized subadditive inequality","author":"Hammersley","year":"1974"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB23","doi-asserted-by":"crossref","first-page":"44","DOI":"10.2307\/1426329","article-title":"The probabilities of rooted tree-shapes generated by random bifurcation","volume":"3","author":"Harding","year":"1971","journal-title":"Adv. Appl. Probab."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB24","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0012-365X(76)90058-3","article-title":"A note on the edges of the n-cube","volume":"14","author":"Hart","year":"1976","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB25","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1287\/moor.9.2.301","article-title":"Dichotomous search for random objects on an interval","volume":"9","author":"Hassin","year":"1984","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB26","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0377-2217(92)90237-4","article-title":"Asymptotic analysis of dichotomous search with search and travel costs","volume":"58","author":"Hassin","year":"1992","journal-title":"European J. Oper. Res."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB27","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1080\/02331939008843538","article-title":"On dichotomous search with direction-dependent costs for a uniformly hidden object","volume":"21","author":"Hinderer","year":"1990","journal-title":"Optimization"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB28","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0377-2217(94)90265-8","article-title":"On polychotomous search problem","volume":"73","author":"Hinderer","year":"1994","journal-title":"European J. Oper. Res."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB29","series-title":"ACM Symposium on Theory of Computing (STOC\u201982)","first-page":"296","article-title":"Notes on merging networks","author":"Hong","year":"1982"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB30","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1002\/(SICI)1098-2418(199607)8:4<319::AID-RSA3>3.0.CO;2-0","article-title":"Limit theorems for mergesort","volume":"8","author":"Hwang","year":"1996","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB31","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1080\/01621459.1981.10477746","article-title":"An optimal hierarchical procedure for a modified binomial group-testing problem","volume":"76","author":"Hwang","year":"1981","journal-title":"J. Amer. Statist. Assoc."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB32","unstructured":"H.-K. Hwang, J.-M. Steyaert, On the number of heaps and the cost of heap construction, Colloquium on Mathematics and Computer Science 2002 (Versailles), accepted."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB33","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF01293485","article-title":"New primal and dual matching heuristics","volume":"13","author":"J\u00fcnger","year":"1995","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB34","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1016\/0022-247X(85)90170-2","article-title":"Recurrence relations based on minimization and maximization","volume":"109","author":"Kapoor","year":"1985","journal-title":"J. Math. Anal. Appl."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB35","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1145\/65950.65955","article-title":"Optimum lopsided binary trees","volume":"36","author":"Kapoor","year":"1989","journal-title":"J. Assoc. Comput. Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB36","unstructured":"D.E. Knuth, Mathematical analysis of algorithms, in: Information Processing\u201971, Proceedings of IFIP Congress, Ljubljana, 1971, Vol. 1: Foundations and Systems, Amsterdam, North-Holland, 1972, pp. 19\u201327."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB37","series-title":"The Art of Computer Programming, Volume III\u2014Sorting and Searching","author":"Knuth","year":"1998"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-0000(86)90001-2","article-title":"Binary trees and uniform distribution of traffic cutback","volume":"32","author":"Li","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB39","doi-asserted-by":"crossref","first-page":"1188","DOI":"10.1137\/0218079","article-title":"Solution of a divide-and-conquer maximin recurrence","volume":"18","author":"Li","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB40","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0203020","article-title":"The number of 1's in binary integers","volume":"3","author":"McIlroy","year":"1974","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0117001","article-title":"Some theorems on sorting","volume":"17","author":"Morris","year":"1969","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB42","first-page":"127","article-title":"A dichotomous search","volume":"14","author":"Murakami","year":"1971","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB43","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF00047005","article-title":"Search","volume":"25","author":"O'Geran","year":"1991","journal-title":"Acta Appl. Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB44","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1007\/BF01294131","article-title":"Bottom-up mergesort\u2014a detailed analysis","volume":"14","author":"Panny","year":"1995","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB45","doi-asserted-by":"crossref","unstructured":"M.J. Pelling, D.G. Rogers, A problem in the design of electrical circuits, a generalized subadditive inequality and the recurrence relation j(n,m)=j ([n\/2], m)+j ([n+1\/2], m)+(j n, m\u22121), Lecture Notes in Mathematics, Vol. 622, Springer, Berlin, New York, 1977, pp. 153\u2013169.","DOI":"10.1007\/BFb0069190"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB46","first-page":"29","article-title":"A combinatorial problem in the design of electrical circuits","volume":"4","author":"Pelling","year":"1980","journal-title":"Southeast Asian Bull. Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB47","doi-asserted-by":"crossref","first-page":"1361","DOI":"10.1137\/0524079","article-title":"An elementary approach to some analytic asymptotics","volume":"24","author":"Pippenger","year":"1993","journal-title":"SIAM J. Math. Anal."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB48","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1145\/361405.361423","article-title":"A sorting problem and its complexity","volume":"15","author":"Pohl","year":"1972","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB49","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0210050","article-title":"On a greedy heuristic for complete matching","volume":"10","author":"Reingold","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB50","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1109\/TSE.1981.234519","article-title":"Tidier drawings of trees","volume":"7","author":"Reingold","year":"1981","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB51","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1145\/375827.375837","article-title":"Improved master theorems for divide-and-conquer recurrences","volume":"48","author":"Roura","year":"2001","journal-title":"J. Assoc. Comput. Math."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB52","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0020-0190(86)90148-1","article-title":"Exact balancing is not always good","volume":"22","author":"Snir","year":"1986","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB53","doi-asserted-by":"crossref","unstructured":"J.M. Steele, Probability theory and combinatorial optimization, CBMS-NSF Regional Conf., Series in Applied Mathematics, Vol. 69, SIAM, PA, 1997.","DOI":"10.1137\/1.9781611970029"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB54","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0020-0190(84)90086-3","article-title":"How evenly should one divide to conquer quickly?","volume":"19","author":"Walsh","year":"1984","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB55","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1006\/jagm.1996.0839","article-title":"Tighter bounds on the solution of a divide-and-conquer maximin recurrence","volume":"23","author":"Wang","year":"1997","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(02)00066-X_BIB56","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/1006036","article-title":"A linear search problem","volume":"6","author":"Wong","year":"1964","journal-title":"SIAM Rev."},{"key":"10.1016\/S0304-3975(02)00066-X_BIB57","doi-asserted-by":"crossref","unstructured":"J.E. Yukich, Probability theory of classical Euclidean optimization problems, Lecture Notes in Mathematics, Vol. 1675, Springer, Berlin, 1998.","DOI":"10.1007\/BFb0093472"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750200066X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750200066X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,12]],"date-time":"2023-04-12T16:57:34Z","timestamp":1681318654000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439750200066X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["S030439750200066X"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(02)00066-x","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}