Exact asymptotics of divide-and-conquer recurrences

Philippe Flajolet; Mordecai Golin

doi:10.1007/3-540-56939-1_68

Exact asymptotics of divide-and-conquer recurrences

Philippe Flajolet, Mordecai Golin

Department of Computer Science and Engineering

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

8 Citations (Scopus)

Abstract

The divide-and-conquer principle is a majol paradigm of algorithms design. Corresponding cost functions satisfy recurrences that directly reflect the decomposition mechanism used in the algorithm. This work shows that periodicity phenomena, often of a fractal nature, are ubiquitous in the performances of these algorithms. Mellin transforms and Dirichlet series are used to attain precise asymptotic estimates. The method is illustrated by a detailed average case, variance and distribution analysis of the classic top-down recursive mergesort algorithm. The approach is applicable to a large number of divide-and-conquer recurrences, and a general theorem is obtained when tile partitioningmerging toll of a divide-and-conquer algorithm is a sublinear function. As another illustration the method is also used to provide an exact analysis of an efficient maxima-finding algorithm.. Exact Asymptotics of Divide-and-Conquer Recurrences Philippe FLAJOLET 1 and Mordecai GOLIN 2 1 Algorithms Project, INRIA Rocquencourt, F-78153 Le Chesnay, France 2 Department of Computer Science, tIKUST, Clear Water Bay, Kowloon, Hong Kong Abstract. The divide-and-conquer principle is a majol paradigm of algorithms design. Corresponding cost functions satisfy recurrences that directly reflect the decomposition mechanism used in the algorithm. This work shows that periodicity phenomena, often of a fractal nature, are ubiquitous in the performances of these algorithms. Mellin transforms and Dirichlet series are used to attain precise asymptotic estimates. The method is illustrated by a detailed average case, variance and distribution analysis of the classic top-down recursive mergesort algorithm. The approach is applicable to a large number of divide-and-conquer recurrences, and a general theorem is obtained when tile partitioningmerging toll of a divide-and-conquer algorithm is a sublinear function. As another illustration the method is also used to provide an exact analysis of an efficient maxima-finding algorithm.

Original language	English
Title of host publication	Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings
Editors	Andrzej Lingas, Rolf Karlsson, Svante Carlsson
Publisher	Springer Verlag
Pages	137-149
Number of pages	13
ISBN (Print)	9783540569398
DOIs	https://doi.org/10.1007/3-540-56939-1_68
Publication status	Published - 1993
Event	20th International Colloquium on Automata, Languages and Programming, ICALP 1993 - Lund, Sweden Duration: 5 Jul 1993 → 9 Jul 1993

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	700 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Colloquium on Automata, Languages and Programming, ICALP 1993
Country/Territory	Sweden
City	Lund
Period	5/07/93 → 9/07/93

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.

Access to Document

10.1007/3-540-56939-1_68

Cite this

Flajolet, P., & Golin, M. (1993). Exact asymptotics of divide-and-conquer recurrences. In A. Lingas, R. Karlsson, & S. Carlsson (Eds.), Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings (pp. 137-149). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 700 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-56939-1_68

Flajolet, Philippe ; Golin, Mordecai. / Exact asymptotics of divide-and-conquer recurrences. Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings. editor / Andrzej Lingas ; Rolf Karlsson ; Svante Carlsson. Springer Verlag, 1993. pp. 137-149 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ab8078a8e81240808ae5db9df7e6b87a,

title = "Exact asymptotics of divide-and-conquer recurrences",

abstract = "The divide-and-conquer principle is a majol paradigm of algorithms design. Corresponding cost functions satisfy recurrences that directly reflect the decomposition mechanism used in the algorithm. This work shows that periodicity phenomena, often of a fractal nature, are ubiquitous in the performances of these algorithms. Mellin transforms and Dirichlet series are used to attain precise asymptotic estimates. The method is illustrated by a detailed average case, variance and distribution analysis of the classic top-down recursive mergesort algorithm. The approach is applicable to a large number of divide-and-conquer recurrences, and a general theorem is obtained when tile partitioningmerging toll of a divide-and-conquer algorithm is a sublinear function. As another illustration the method is also used to provide an exact analysis of an efficient maxima-finding algorithm.. Exact Asymptotics of Divide-and-Conquer Recurrences Philippe FLAJOLET 1 and Mordecai GOLIN 2 1 Algorithms Project, INRIA Rocquencourt, F-78153 Le Chesnay, France 2 Department of Computer Science, tIKUST, Clear Water Bay, Kowloon, Hong Kong Abstract. The divide-and-conquer principle is a majol paradigm of algorithms design. Corresponding cost functions satisfy recurrences that directly reflect the decomposition mechanism used in the algorithm. This work shows that periodicity phenomena, often of a fractal nature, are ubiquitous in the performances of these algorithms. Mellin transforms and Dirichlet series are used to attain precise asymptotic estimates. The method is illustrated by a detailed average case, variance and distribution analysis of the classic top-down recursive mergesort algorithm. The approach is applicable to a large number of divide-and-conquer recurrences, and a general theorem is obtained when tile partitioningmerging toll of a divide-and-conquer algorithm is a sublinear function. As another illustration the method is also used to provide an exact analysis of an efficient maxima-finding algorithm.",

author = "Philippe Flajolet and Mordecai Golin",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 20th International Colloquium on Automata, Languages and Programming, ICALP 1993 ; Conference date: 05-07-1993 Through 09-07-1993",

year = "1993",

doi = "10.1007/3-540-56939-1\_68",

language = "English",

isbn = "9783540569398",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "137--149",

editor = "Andrzej Lingas and Rolf Karlsson and Svante Carlsson",

booktitle = "Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings",

}

Flajolet, P & Golin, M 1993, Exact asymptotics of divide-and-conquer recurrences. in A Lingas, R Karlsson & S Carlsson (eds), Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 700 LNCS, Springer Verlag, pp. 137-149, 20th International Colloquium on Automata, Languages and Programming, ICALP 1993, Lund, Sweden, 5/07/93. https://doi.org/10.1007/3-540-56939-1_68

Exact asymptotics of divide-and-conquer recurrences. / Flajolet, Philippe; Golin, Mordecai.
Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings. ed. / Andrzej Lingas; Rolf Karlsson; Svante Carlsson. Springer Verlag, 1993. p. 137-149 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 700 LNCS).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Exact asymptotics of divide-and-conquer recurrences

AU - Flajolet, Philippe

AU - Golin, Mordecai

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1993.

PY - 1993

Y1 - 1993

N2 - The divide-and-conquer principle is a majol paradigm of algorithms design. Corresponding cost functions satisfy recurrences that directly reflect the decomposition mechanism used in the algorithm. This work shows that periodicity phenomena, often of a fractal nature, are ubiquitous in the performances of these algorithms. Mellin transforms and Dirichlet series are used to attain precise asymptotic estimates. The method is illustrated by a detailed average case, variance and distribution analysis of the classic top-down recursive mergesort algorithm. The approach is applicable to a large number of divide-and-conquer recurrences, and a general theorem is obtained when tile partitioningmerging toll of a divide-and-conquer algorithm is a sublinear function. As another illustration the method is also used to provide an exact analysis of an efficient maxima-finding algorithm.. Exact Asymptotics of Divide-and-Conquer Recurrences Philippe FLAJOLET 1 and Mordecai GOLIN 2 1 Algorithms Project, INRIA Rocquencourt, F-78153 Le Chesnay, France 2 Department of Computer Science, tIKUST, Clear Water Bay, Kowloon, Hong Kong Abstract. The divide-and-conquer principle is a majol paradigm of algorithms design. Corresponding cost functions satisfy recurrences that directly reflect the decomposition mechanism used in the algorithm. This work shows that periodicity phenomena, often of a fractal nature, are ubiquitous in the performances of these algorithms. Mellin transforms and Dirichlet series are used to attain precise asymptotic estimates. The method is illustrated by a detailed average case, variance and distribution analysis of the classic top-down recursive mergesort algorithm. The approach is applicable to a large number of divide-and-conquer recurrences, and a general theorem is obtained when tile partitioningmerging toll of a divide-and-conquer algorithm is a sublinear function. As another illustration the method is also used to provide an exact analysis of an efficient maxima-finding algorithm.

AB - The divide-and-conquer principle is a majol paradigm of algorithms design. Corresponding cost functions satisfy recurrences that directly reflect the decomposition mechanism used in the algorithm. This work shows that periodicity phenomena, often of a fractal nature, are ubiquitous in the performances of these algorithms. Mellin transforms and Dirichlet series are used to attain precise asymptotic estimates. The method is illustrated by a detailed average case, variance and distribution analysis of the classic top-down recursive mergesort algorithm. The approach is applicable to a large number of divide-and-conquer recurrences, and a general theorem is obtained when tile partitioningmerging toll of a divide-and-conquer algorithm is a sublinear function. As another illustration the method is also used to provide an exact analysis of an efficient maxima-finding algorithm.. Exact Asymptotics of Divide-and-Conquer Recurrences Philippe FLAJOLET 1 and Mordecai GOLIN 2 1 Algorithms Project, INRIA Rocquencourt, F-78153 Le Chesnay, France 2 Department of Computer Science, tIKUST, Clear Water Bay, Kowloon, Hong Kong Abstract. The divide-and-conquer principle is a majol paradigm of algorithms design. Corresponding cost functions satisfy recurrences that directly reflect the decomposition mechanism used in the algorithm. This work shows that periodicity phenomena, often of a fractal nature, are ubiquitous in the performances of these algorithms. Mellin transforms and Dirichlet series are used to attain precise asymptotic estimates. The method is illustrated by a detailed average case, variance and distribution analysis of the classic top-down recursive mergesort algorithm. The approach is applicable to a large number of divide-and-conquer recurrences, and a general theorem is obtained when tile partitioningmerging toll of a divide-and-conquer algorithm is a sublinear function. As another illustration the method is also used to provide an exact analysis of an efficient maxima-finding algorithm.

UR - https://www.scopus.com/pages/publications/21144470474

U2 - 10.1007/3-540-56939-1_68

DO - 10.1007/3-540-56939-1_68

M3 - Conference Paper published in a book

AN - SCOPUS:21144470474

SN - 9783540569398

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 137

EP - 149

BT - Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings

A2 - Lingas, Andrzej

A2 - Karlsson, Rolf

A2 - Carlsson, Svante

PB - Springer Verlag

T2 - 20th International Colloquium on Automata, Languages and Programming, ICALP 1993

Y2 - 5 July 1993 through 9 July 1993

ER -

Flajolet P, Golin M. Exact asymptotics of divide-and-conquer recurrences. In Lingas A, Karlsson R, Carlsson S, editors, Automata, Languages and Programming - 20th International Colloquium, ICALP 1993, Proceedings. Springer Verlag. 1993. p. 137-149. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-56939-1_68

Exact asymptotics of divide-and-conquer recurrences

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this