Access Restriction

Author Drmota, Michael ♦ Szpankowski, Wojciech
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2013
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Boncelet’s data compression algorithm ♦ Dirichlet series ♦ Divide-and-conquer recurrence ♦ Karatsuba algorithm ♦ Mellin-Perron formula ♦ Strassen algorithm ♦ Tauberian theorem ♦ Mergesort
Abstract $\textit{Divide-and-conquer}$ recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences, namely for some known sequence $a_{n}$ and given $b_{j},$ $b_{j},$ $p_{j}$ and $Δ_{j},$ $Δ_{j},$ present some challenges. The discrete nature of this recurrence (represented by the floor and ceiling functions) introduces certain oscillations not captured by the traditional Master Theorem, for example due to Akra and Bazzi [1998] who primary studied the continuous version of the recurrence. We apply powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara to provide a complete and precise solution to this basic computer science recurrence. We illustrate applicability of our results on several examples including a popular and fast arithmetic coding algorithm due to Boncelet for which we estimate its average redundancy and prove the Central Limit Theorem for the phrase length. To the best of our knowledge, $\textit{discrete}$ divide and conquer recurrences were not studied in this generality and such detail; in particular, this allows us to compare the redundancy of Boncelet’s algorithm to the (asymptotically) optimal Tunstall scheme.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2013-06-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 60
Issue Number 3
Page Count 49
Starting Page 1
Ending Page 49

Open content in new tab

   Open content in new tab
Source: ACM Digital Library