{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T06:33:45Z","timestamp":1775802825162,"version":"3.50.1"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,10,25]],"date-time":"2017-10-25T00:00:00Z","timestamp":1508889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"Isaac Newton Institute for Mathematical Sciences EPSCR","award":["EP\/K032208\/1"],"award-info":[{"award-number":["EP\/K032208\/1"]}]},{"name":"Simons Foundation and a grant from the Knut and Alice Wallenberg Foundation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>\n            Divide-and-conquer recurrences of the form\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) =\n            <jats:italic>f<\/jats:italic>\n            (\u230a n\/2\u230b ) +\n            <jats:italic>f<\/jats:italic>\n            ( \u2308 n\/2\u2309 ) +\n            <jats:italic>g<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) (\n            <jats:italic>n<\/jats:italic>\n            \u2a7e 2), with\n            <jats:italic>g<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) and\n            <jats:italic>f<\/jats:italic>\n            (1) given, appear very frequently in the analysis of computer algorithms and related areas. While most previous methods and results focus on simpler crude approximation to the solution, we show that the solution always satisfies the simple\n            <jats:italic>identity<\/jats:italic>\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) =\n            <jats:italic>n<\/jats:italic>\n            <jats:italic>P<\/jats:italic>\n            (log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            ) \u2212\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) under an optimum (iff) condition on\n            <jats:italic>g<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ). This form is not only an identity but also an asymptotic expansion because\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) is of a smaller order than linearity. Explicit forms for the\n            <jats:italic>continuous<\/jats:italic>\n            periodic function\n            <jats:italic>P<\/jats:italic>\n            are provided. We show how our results can be easily applied to many dozens of concrete examples collected from the literature and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary but leads to the strongest types of results for all examples to which our theory applies.\n          <\/jats:p>","DOI":"10.1145\/3127585","type":"journal-article","created":{"date-parts":[[2017,10,26]],"date-time":"2017-10-26T14:19:33Z","timestamp":1509027573000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9410-6476","authenticated-orcid":false,"given":"Hsien-Kuei","family":"Hwang","sequence":"first","affiliation":[{"name":"Academia Sinica, Taipei, Taiwan"}]},{"given":"Svante","family":"Janson","sequence":"additional","affiliation":[{"name":"Uppsala University, Uppsala, Sweden"}]},{"given":"Tsung-Hsi","family":"Tsai","sequence":"additional","affiliation":[{"name":"Academia Sinica, Taipei, Taiwan"}]}],"member":"320","published-online":{"date-parts":[[2017,10,25]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"A. V. Aho J. E. Hopcroft and J. D. Ullman. 1975. The Design and Analysis of Computer Algorithms. Second printing. Addison-Wesley Publishing Co. Reading MA.   A. V. Aho J. E. Hopcroft and J. D. Ullman. 1975. The Design and Analysis of Computer Algorithms. Second printing. Addison-Wesley Publishing Co. Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018353700639"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14321\/realanalexch.37.1.0001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90001-V"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"J.-P. Allouche and J. Shallit. 2003. Automatic Sequences. Theory Applications Generalizations Cambridge University Press Cambridge UK.   J.-P. Allouche and J. Shallit. 2003. Automatic Sequences. Theory Applications Generalizations Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511546563"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00090-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20053"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626402000999"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008861.1008865"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90051-0"},{"key":"e_1_2_1_11_1","unstructured":"G. Brassard and P. Bratley. 1988. Algorithmics. Theory and Practice. Prentice Hall Inc. Englewood Cliffs NJ.   G. Brassard and P. Bratley. 1988. Algorithmics. Theory and Practice. Prentice Hall Inc. Englewood Cliffs NJ."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392815"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-71-03869-5"},{"key":"e_1_2_1_14_1","first-page":"377","volume-title":"Proceedings of American Conference on Applied Mathematics","author":"Cha S.-H.","year":"2012"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626497000292"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0986"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.08.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-PS213"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10005"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240235"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_2_1_22_1","unstructured":"T. Cormen C. Leiserson and R. Rivest. 1990. Introduction to Algorithms. McGraw-Hill New York NY.   T. Cormen C. Leiserson and R. Rivest. 1990. Introduction to Algorithms. McGraw-Hill New York NY."},{"key":"e_1_2_1_23_1","first-page":"31","article-title":"Sur la fonction sommatoire de la fonction \u201csomme des chiffres","volume":"21","author":"Delange H.","year":"1975","journal-title":"Enseignement Math."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280782"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050205"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009256"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487241.2487242"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0334270000007633"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.036"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2307\/3214289"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)E0211-L"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1987.126.227"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"P.\n      Flajolet\n     and \n      M.\n      Golin\n  . \n  1993\n  . Exact asymptotics of divide-and-conquer recurrences. In Automata Languages and Programming (Lund 1993) 137--149 Lecture Notes in Computer Sciences Vol. \n  700 Springer Berlin.   P. Flajolet and M. Golin. 1993. Exact asymptotics of divide-and-conquer recurrences. In Automata Languages and Programming (Lund 1993) 137--149 Lecture Notes in Computer Sciences Vol. 700 Springer Berlin.","DOI":"10.1007\/3-540-56939-1_68"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01177551"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00065-Y"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"P. Flajolet and L. Ramshaw. 1980. A note on Gray code and odd-even merge. SIAM J. Comput. 142--158.  P. Flajolet and L. Ramshaw. 1980. A note on Gray code and odd-even merge. SIAM J. Comput. 142--158.","DOI":"10.1137\/0209014"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(74)90176-0"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-65-1-85-96"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-004-0561-x"},{"key":"e_1_2_1_40_1","unstructured":"D. H. Greene and D. E. Knuth. 2008. Reprint of the third (1990) edition. Birkh\u00e4user Boston MA.  D. H. Greene and D. E. Knuth. 2008. Reprint of the third (1990) edition. Birkh\u00e4user Boston MA."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410003646X"},{"key":"e_1_2_1_42_1","unstructured":"J. M. Hammersley and G. R. Grimmett. 1974. Maximal solutions of the generalized subadditive inequality. In Stochastic Geometry (A Tribute to the Memory of Rollo Davidson) 270--284 Wiley London.  J. M. Hammersley and G. R. Grimmett. 1974. Maximal solutions of the generalized subadditive inequality. In Stochastic Geometry (A Tribute to the Memory of Rollo Davidson) 270--284 Wiley London."},{"key":"e_1_2_1_43_1","volume-title":"Computer Science Press","author":"Horowitz E.","year":"1978"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(95)00236-7"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009238"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050147"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v16-858"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970138390X"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00066-X"},{"key":"e_1_2_1_50_1","volume-title":"Exact and asymptotic solutions of the recurrence f(n) &equals","author":"Hwang H.-K.","year":"2017"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5802\/jtnb.798"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/261342.261350"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.2983"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"M. Kuczma B. Choczewski and R. Ger. 1990. Iterative Functional Equations. Cambridge University Press Cambridge UK.  M. Kuczma B. Choczewski and R. Ger. 1990. Iterative Functional Equations. Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9781139086639"},{"key":"e_1_2_1_55_1","volume-title":"Notes on better master theorems for divide-and-conquer recurrences. MIT Lecture Notes","author":"Leighton T."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218079"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSCS.2013.73"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117001"},{"key":"e_1_2_1_60_1","first-page":"106","volume-title":"IEEE International Symposium on Information Theory Proceedings (ISIT\u201910)","author":"Oh S. Y."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.07.025"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/361405.361423"},{"key":"e_1_2_1_64_1","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and M. I. Shamos. 1985. Computational Geometry. An Introduction. Springer-Verlag New York NY.   F. P. Preparata and M. I. Shamos. 1985. Computational Geometry. An Introduction. Springer-Verlag New York NY.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_65_1","unstructured":"P. W. Purdom and C. A. Brown. 1985. The Analysis of Algorithms. Holt Rinehart 8 Winston New York NY.   P. W. Purdom and C. A. Brown. 1985. The Analysis of Algorithms. Holt Rinehart 8 Winston New York NY."},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","volume-title":"Adventures in Stochastic Processes","author":"Resnick S.","DOI":"10.1007\/978-1-4612-0387-2"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375837"},{"key":"e_1_2_1_68_1","volume-title":"Mastering the Master Theorem","author":"Sch\u00f6ning U.","year":"2000"},{"key":"e_1_2_1_69_1","unstructured":"R. Sedgewick. 1980. Quicksort. Garland New York NY.  R. Sedgewick. 1980. Quicksort. Garland New York NY."},{"key":"e_1_2_1_70_1","volume-title":"The On-Line Encyclopedia of Integer Sequences. Retrieved","author":"N. J.","year":"2017"},{"key":"e_1_2_1_71_1","unstructured":"R. Stephan. 2004. Some divide-and-conquer sequences with (relatively) simple ordinary generating functions.  R. Stephan. 2004. Some divide-and-conquer sequences with (relatively) simple ordinary generating functions."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/0132060"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212008"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1004"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240583"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00076-2"},{"key":"e_1_2_1_77_1","volume-title":"Theory and Applications of Models of Computation, 14--26, LNCS","author":"Yap C."},{"key":"e_1_2_1_78_1","unstructured":"E. T. Whittaker and G. N. Watson. 1996. A Course of Modern Analysis reprint of the fourth (1927) edition. Cambridge University Press Cambridge UK.  E. T. Whittaker and G. N. Watson. 1996. A Course of Modern Analysis reprint of the fourth (1927) edition. Cambridge University Press Cambridge UK."},{"key":"e_1_2_1_79_1","volume-title":"Trigonometric Series","author":"Zygmund A."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3127585","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3127585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:00Z","timestamp":1750212660000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3127585"}},"subtitle":["Theory and Applications"],"short-title":[],"issued":{"date-parts":[[2017,10,25]]},"references-count":77,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3127585"],"URL":"https:\/\/doi.org\/10.1145\/3127585","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,25]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}