research-article

Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications

Authors:

Hsien-Kuei Hwang,

Tsung-Hsi TsaiAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 13, Issue 4

Article No.: 47, Pages 1 - 43

https://doi.org/10.1145/3127585

Published: 25 October 2017 Publication History

Abstract

Divide-and-conquer recurrences of the form f(n) = f (⌊ n/2⌋ ) + f ( ⌈ n/2⌉ ) + g(n) (n⩾ 2), with g(n) and f(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 identity f(n) = n P(log₂n) − Q(n) under an optimum (iff) condition on g(n). This form is not only an identity but also an asymptotic expansion because Q(n) is of a smaller order than linearity. Explicit forms for the continuous periodic function P 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.

References

[1]

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.

Digital Library

[2]

M. Akra and L. Bazzi. 1998. On the solution of linear recurrence equations, Comput. Optim. Appl. 10, 195--210.

Digital Library

[3]

P. C. Allaart and K. Kawamura. 2012. The Takagi function: a survey. Real Anal. Exchange 37, 1--54.

[4]

J.-P. Allouche and J. Shallit. 1992. The ring of k-regular sequences, Theoret. Comput. Sci. 98, 163--197.

Digital Library

[5]

J.-P. Allouche and J. Shallit. 2003. Automatic Sequences. Theory, Applications, Generalizations, Cambridge University Press, Cambridge UK.

Digital Library

[6]

J.-P. Allouche and J. Shallit. 2003. The ring of -regular sequences. II. Words, Theoret. Comput. Sci. 307, 3--29.

Digital Library

[7]

Z.-D. Bai, L. Devroye, H.-K. Hwang and T.-H. Tsai. 2005. Maxima in hypercubes. Random Structures Algorithms 27, 290--309.

Digital Library

[8]

B. Beauquier and E. Darrot. 2002. On arbitrary size Waksman networks and their vulnerability. Parallel Process. Lett. 12, 287--296.

[9]

J. L. Bentley, D. Haken, and J. B. Saxe. 1980. A general method for solving divide-and-conquer recurrences. ACM SIGACT News 12.3, 36--44.

Digital Library

[10]

J. L. Bentley and M. I. Shamos. 1978. Divide and conquer for linear expected time. Information Processing Lett. 7, 87--91.

[11]

G. Brassard and P. Bratley. 1988. Algorithmics. Theory and Practice. Prentice Hall, Inc., Englewood Cliffs, NJ.

Digital Library

[12]

L. Carleson. 1966. On convergence and growth of partial sums of Fourier series. Acta Math. 116, 135--157.

[13]

L. Carlitz. 1971. A sorting function. Duke Math. J. 38, 561--568.

[14]

S.-H. Cha. 2012. On integer sequences derived from balanced k-ary trees. In Proceedings of American Conference on Applied Mathematics, pp. 377--381.

Digital Library

[15]

C. Chang and R. Melhem. 1997. Arbitrary size Benes networks. Parallel Process. Lett. 7, 279--284.

[16]

W.-M. Chen, H.-K. Hwang, G.-H. Chen. 1999. The cost distribution of queue-mergesort, optimal mergesorts, and power-of-2 rules. J. Algorithms 30, 423--448.

Digital Library

[17]

W.-M. Chen, H.-K. Hwang and T.-H. Tsai. 2012. Maxima-finding algorithms for multidimensional samples: a two-phase approach. Comput. Geom. 45, 33--53.

Digital Library

[18]

L. H. Y. Chen, H.-K. Hwang and V. Zacharovas. 2014. Distribution of the sum-of-digits function of random integers: a survey. Probab. Surv. 11, 177--236.

[19]

H.-H. Chern and H.-K. Hwang. 2001. Phase changes in random m-ary search trees and generalized quicksort, Random Structures Algorithms 19, 316--358.

Digital Library

[20]

H.-H. Chern, M. Fuchs, and H.-K. Hwang. 2007. Phase changes in random point quadtrees. ACM Trans. Algorithms 3, Art. 12, 51 pp.

Digital Library

[21]

K. L. Clarkson and P. W. Shor. 1989. Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387--421.

Digital Library

[22]

T. Cormen, C. Leiserson, and R. Rivest. 1990. Introduction to Algorithms. McGraw-Hill, New York, NY.

Digital Library

[23]

H. Delange. 1975. Sur la fonction sommatoire de la fonction “somme des chiffres.” Enseignement Math. 21, 31--47.

[24]

L. Devroye. 1983. Moment inequalities for random variables in computational geometry. 1983. Computing 30 111--119.

[25]

L. Devroye. 1994. On random Cartesian trees. Random Structures Algorithms 5, 305--327.

Digital Library

[26]

L. Devroye. 1999. A note on the expected time for finding maxima by list algorithms. Algorithmica 23, 97--108.

[27]

M. Drmota and W. Szpankowski. 2013. A master theorem for discrete divide and conquer recurrences. J. ACM 60, Art. 16, 49 pp.

Digital Library

[28]

S. Dube. 1995. Using fractal geometry for solving divide-and-conquer recurrences. J. Austral. Math. Soc. Ser. B 37, 145--171.

[29]

P. Dumas. 2014. Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated. Theoret. Comput. Sci. 548, 25--53.

[30]

R. A. Dwyer. 1988. On the convex hull of random points in a polytope. J. Appl. Probab. 25, 688--699.

[31]

W. M. Dymàček and T. Whaley. 1995. Generating strings for bipartite Steinhaus graphs. Discrete Math. 141, 95--107.

Digital Library

[32]

P. Erdős, A. Hildebrand, A. Odlyzko, P. Pudaite and B. Reznick. 1987. The asymptotic behavior of a family of sequences, Pacific J. Math. 126, 227--241.

[33]

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.

Digital Library

[34]

P. Flajolet and M. Golin. 1994. Mellin transforms and asymptotics. The mergesort recurrence, Acta Inform. 31, 673--696.

Digital Library

[35]

P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger, and R. F. Tichy. 1994. Mellin transforms and asymptotics: digital sums. Theoret. Comput. Sci. 123, 291--314.

Digital Library

[36]

P. Flajolet and L. Ramshaw. 1980. A note on Gray code and odd-even merge. SIAM J. Comput. 142--158.

[37]

M. L. Fredman and D. E. Knuth. 1974. Recurrence relations based on minimization. J. Math. Anal. Appl. 48, 534--559.

[38]

P. J. Grabner. 1993. Completely -multiplicative functions: the Mellin transform approach. Acta Arith. 65, 85--96.

[39]

P. J. Grabner and H.-K. Hwang. 2005. Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence. Constr. Approx. 21, 149--179.

[40]

D. H. Greene and D. E. Knuth. 2008. Reprint of the third (1990) edition. Birkhäuser, Boston, MA.

[41]

J. M. Hammersley. 1962. Generalization of the fundamental theorem on sub-additive functions. Proc. Cambridge Philos. Soc. 58, 235--238.

[42]

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.

[43]

E. Horowitz and S. Sahni. 1978. Fundamentals of Computer Algorithms, Computer Science Press, Rockville, MD, 1978.

Digital Library

[44]

H.-K. Hwang. 1996. Asymptotic expansion for the Lebesgue constants of the Walsh system. J. Comput. Appl. Math. 71, 237--243.

Digital Library

[45]

H.-K. Hwang. 1998. Asymptotics of divide-and-conquer recurrences: Batcher’s sorting algorithm and a minimum Euclidean matching heuristic. Algorithmica 22, 529--546.

[46]

H.-K. Hwang. 1998. Asymptotic expansions of the mergesort recurrences, Acta Inform. 35, 911--919.

[47]

H.-K. Hwang and S. Janson. 2011. A central limit theorem for random ordered factorizations of integers. Electron. J. Probab. 16, 347--361.

[48]

H.-K. Hwang and R. Neininger. 2002. Phase change of limit laws in the quicksort recurrence under varying toll functions. SIAM J. Comput. 31, 1687--1722.

Digital Library

[49]

H.-K. Hwang and T.-H. Tsai. 2003. An asymptotic theory for recurrence relations based on minimization and maximization. Theoret. Comput. Sci. 290, 1475--1501.

Digital Library

[50]

H.-K. Hwang, S. Janson, and T.-H. Tsai. 2017. Exact and asymptotic solutions of the recurrence f(n) = αf (&lfloor; &fracn2;&rfloor; ) + βf ( &lceil; &fracn2;&rceil; ) + g(n): theory and applications. In preparation (2017).

[51]

Y. Kamiya and L. Murata. 2012. Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes. J. Théor. Nombres Bordeaux 24, 307--337.

[52]

M.-Y. Kao. 1997. Multiple-size divide-and-conquer recurrences. SIGACT News, 28, 67--69.

Digital Library

[53]

J. Kieffer. 2012. Asymptotics of divide-and-conquer recurrences via iterated function systems. In 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’12), Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, AQ, pp. 55--66, 2012.

[54]

M. Kuczma, B. Choczewski and R. Ger. 1990. Iterative Functional Equations. Cambridge University Press, Cambridge, UK.

[55]

T. Leighton. 1996. Notes on better master theorems for divide-and-conquer recurrences. MIT Lecture Notes, Cambridge, MA.

[56]

Z. Li and E. M. Reingold. 1989. Solution of a divide-and-conquer maximin recurrence. SIAM J. Comput. 18, 1188--1200.

Digital Library

[57]

A.-H. Mogos. 2013. Three variants of the master theorem. 2013. In the 19th International Conference on Control Systems and Computer Science, pp. 162--166, 2013.

Digital Library

[58]

R. Morris. 1969. Some theorems on sorting. SIAM J. Appl. Math. 17, 1--6.

Digital Library

[59]

S. Y. Oh. 2012. Information Theory of Random Trees Induced by Stochastic Grammars. Ph.D. Dissertation. University of Minnesota, Minneapolis, MN.

[60]

S. Y. Oh and J. C. Kieffer. 2010. Fractal compression rate curves in lossless compression of balanced trees. In IEEE International Symposium on Information Theory Proceedings (ISIT’10), pp. 106--110.

[61]

J. Oudinet. 2010. Approches combinatoires pour le test statistique à grande échelle. Ph.D. Thesis, Université de Paris-Sud, Paris.

[62]

J. Oudinet, A. Denise and M.-C. Gaudel. 2013. A new dichotomic algorithm for the uniform random generation of words in regular languages. Theoret. Comput. Sci. 502, 165--176.

Digital Library

[63]

I. Pohl. 1972. A sorting problem and its complexity. Comm. ACM 15, 462--464.

Digital Library

[64]

F. P. Preparata and M. I. Shamos. 1985. Computational Geometry. An Introduction. Springer-Verlag, New York, NY.

Digital Library

[65]

P. W. Purdom and C. A. Brown. 1985. The Analysis of Algorithms. Holt, Rinehart 8 Winston, New York, NY.

Digital Library

[66]

S. Resnick. 1992. Adventures in Stochastic Processes. Birkhäuser Boston, Inc., Boston, MA.

Digital Library

[67]

S. Roura. 2001. Improved master theorems for divide-and-conquer recurrences. J. ACM 48, 170--205.

Digital Library

[68]

U. Schöning. Mastering the Master Theorem. 2000. Bulletin of the EATCS 71, 165--166.

[69]

R. Sedgewick. 1980. Quicksort. Garland, New York, NY.

[70]

N. J. A. Sloane et al. 2017. The On-Line Encyclopedia of Integer Sequences. Retrieved August 13, 2017 from https://oeis.org/somedcgf.html (Version 2004-01-1).

[71]

R. Stephan. 2004. Some divide-and-conquer sequences with (relatively) simple ordinary generating functions.

[72]

K. B. Stolarsky. 1977. Power and exponential sums of digital sums related to binomial coefficient parity. SIAM J. Appl. Math. 32, 717--730.

[73]

K. J. Supowit and E. M. Reingold. 1983. Divide and conquer heuristics for minimum weighted Euclidean matching. SIAM J. Comput. 12, 118--143.

Digital Library

[74]

R. M. Verma. 1994. A general method and a master theorem for divide-and-conquer recurrences with applications. J. Algorithms 16, 67--79.

Digital Library

[75]

R. M. Verma. 1997. General techniques for analyzing recursive algorithms with applications. SIAM J. Comput. 26, 568--581.

Digital Library

[76]

X. Wang and Q. Fu. 1996. A frame for general divide-and-conquer recurrences, Inform. Process. Lett. 59, 45--51.

Digital Library

[77]

C. Yap. 2011. A real elementary approach to the master recurrence and generalizations. In Theory and Applications of Models of Computation, 14--26, LNCS, Vol. 6648, Springer, Berlin.

Digital Library

[78]

E. T. Whittaker and G. N. Watson. 1996. A Course of Modern Analysis, reprint of the fourth (1927) edition. Cambridge University Press, Cambridge, UK.

[79]

A. Zygmund. 2002. Trigonometric Series, third ed., Cambridge University Press, Cambridge, UK.

Cited By

Shi YLuo XJiang Z(2024)Asymptotics on a heriditary recursionAIMS Mathematics10.3934/math.202414699:11(30443-30453)Online publication date: 2024
https://doi.org/10.3934/math.20241469
Alekseyev M(2024)Enumeration of Payphone PermutationsThe American Mathematical Monthly10.1080/00029890.2024.2323961131:6(491-500)Online publication date: 27-Mar-2024
https://doi.org/10.1080/00029890.2024.2323961
Hwang HJanson STsai T(2024)Identities and periodic oscillations of divide-and-conquer recurrences splitting at halfAdvances in Applied Mathematics10.1016/j.aam.2023.102653155(102653)Online publication date: Apr-2024
https://doi.org/10.1016/j.aam.2023.102653
Show More Cited By

Index Terms

Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications

Recommendations

Identities and periodic oscillations of divide-and-conquer recurrences splitting at half
Abstract
We study divide-and-conquer recurrences of the form f ( n ) = α f ( ⌊ n 2 ⌋ ) + β f ( ⌈ n 2 ⌉ ) + g ( n ) ( n ⩾ 2 ) , with g ( n ) and f ( 1 ) given, where α , β ⩾ 0 with α + β > 0; such recurrences appear often in the analysis of computer ...
Asymptotic approximations for the first incomplete elliptic integral near logarithmic singularity

We find two convergent series expansions for Legendre's first incomplete elliptic integral F(@l,k) in terms of recursively computed elementary functions. Both expansions are valid at every point of the unit square 0<@l,k<1. Truncated expansions yield ...
Asymptotic zero distribution of Jacobi-Piñeiro and multiple Laguerre polynomials

We give the asymptotic distribution of the zeros of Jacobi-Piñeiro polynomials and multiple Laguerre polynomials of the first kind. We use the nearest neighbor recurrence relations for these polynomials and a recent result on the ratio asymptotics of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 13, Issue 4

October 2017

333 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3143522

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2017 Owner/Author.

This work is licensed under a Creative Commons Attribution-NonCommercial International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 October 2017

Accepted: 01 July 2017

Received: 01 December 2016

Published in TALG Volume 13, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Isaac Newton Institute for Mathematical Sciences EPSCR
Simons Foundation and a grant from the Knut and Alice Wallenberg Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
334
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shi YLuo XJiang Z(2024)Asymptotics on a heriditary recursionAIMS Mathematics10.3934/math.202414699:11(30443-30453)Online publication date: 2024
https://doi.org/10.3934/math.20241469
Alekseyev M(2024)Enumeration of Payphone PermutationsThe American Mathematical Monthly10.1080/00029890.2024.2323961131:6(491-500)Online publication date: 27-Mar-2024
https://doi.org/10.1080/00029890.2024.2323961
Hwang HJanson STsai T(2024)Identities and periodic oscillations of divide-and-conquer recurrences splitting at halfAdvances in Applied Mathematics10.1016/j.aam.2023.102653155(102653)Online publication date: Apr-2024
https://doi.org/10.1016/j.aam.2023.102653
Coronado TMir ARosselló F(2022)Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent termPLOS ONE10.1371/journal.pone.027444817:11(e0274448)Online publication date: 17-Nov-2022
https://doi.org/10.1371/journal.pone.0274448
Heuberger CKrenn DLipnik G(2022)Asymptotic Analysis of q-Recursive SequencesAlgorithmica10.1007/s00453-022-00950-y84:9(2480-2532)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s00453-022-00950-y
Chyzak FDumas PEmiris IZhi LMantzaflaris A(2020)A Gröbner-basis theory for divide-and-conquer recurrencesProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3404055(99-106)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3373207.3404055
Heuberger CKrenn D(2020)Asymptotic Analysis of Regular SequencesAlgorithmica10.1007/s00453-019-00631-382:3(429-508)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1007/s00453-019-00631-3

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents