A Master Theorem for Discrete Divide and Conquer Recurrences

DOI10.1145/2487241.2487242zbMath1281.68242OpenAlexW2624611589MaRDI QIDQ5395714

Michael Drmota, Wojciech Szpankowski

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2487241.2487242

zbMATH Keywords

Dirichlet seriesTauberian theoremMellin-Perron formuladivide-and-conquer recurrenceKaratsuba algorithmStrassen algorithmmergesortBoncelet's data compression algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Exact enumeration problems, generating functions (05A15) Recurrences (11B37) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (4)

Proving divide and conquer complexities in Isabelle/HOL ⋮ Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus ⋮ Identities and periodic oscillations of divide-and-conquer recurrences splitting at half ⋮ Asymptotic analysis of regular sequences

This page was built for publication: A Master Theorem for Discrete Divide and Conquer Recurrences