A master theorem for discrete divide and conquer recurrences

MaRDI QIDQ5365047zbMATH OpenFDO

Authors Michael Drmota, Wojciech Szpankowski

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133064

zbMATH Keywords

Boncelet's data compression algorithmDirichlet seriesdivide-and-conquer recurrenceMellin-Perron formulaTauberian theorem

Mathematics Subject Classification ID

Recurrences (11B37) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms (68W40)

Recommendations

• A master theorem for discrete divide and conquer recurrences
• scientific article; zbMATH DE number 7647200
• A General Method and a Master Theorem for Divide-and-Conquer Recurrences with Applications
• An improved master theorem for divide-and-conquer recurrences
• Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications

Cited in

(9)

• The optimality of a certain purely recursive dissection for a sequentially n-divisible square
• Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated
• Exact asymptotics of divide-and-conquer recurrences
• scientific article; zbMATH DE number 833703 (Why is no real title available?)
• A master theorem for discrete divide and conquer recurrences
• scientific article; zbMATH DE number 7647200 (Why is no real title available?)
• The enumeration of prudent polygons by area and its unusual asymptotics

This page was built for publication: A master theorem for discrete divide and conquer recurrences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5365047)