A Master Theorem for Discrete Divide and Conquer Recurrences

A Master Theorem for Discrete Divide and Conquer Recurrences,Michael Drmota,Wojciech Szpankowski

A Master Theorem for Discrete Divide and Conquer Recurrences   (Citations: 1)
BibTex | RIS | RefWorks Download
Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences, namely T(n) = an + m X j=1 bjT (⌊pjn + �j⌋) for some known sequence an and given bj, pj andj, present some challenges. The discrete nature of this recurrence (rep- resented by the floor function) introduces certain oscillations not captured by the traditional Master Theorem, for exam- ple due to Akra and Bazzi who primary studied the con- tinuous version of the recurrence. We apply powerful tech- niques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara to pro- vide 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. To the best of our knowledge, discrete divide and conquer recurrences were not studied in this gen- erality and such detail; in particular, this allows us to com- pare the redundancy of Boncelet's algorithm to the (asymp- totically) optimal Tunstall scheme.
Conference: ACM-SIAM Symposium on Discrete Algorithms - SODA , pp. 342-361, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: