Identities and periodic oscillations of divide-and-conquer recurrences splitting at half

DOI10.1016/J.AAM.2023.102653MaRDI QIDQ6153612zbMATH OpenFDO

Authors Hsien-Kuei Hwang, Svante Janson, Tsung-Hsi Tsai

Publication date 14 February 2024

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.10968

zbMATH Keywords

analysis of algorithmsasymptotic expansiondivide-and-conquerFourier seriesHölder continuityidentityinterpolationLipschitz continuitymaster theoremsMellin transformperiodic equivalenceperiodic functionrecurrence relationuniform continuity

Mathematics Subject Classification ID

Recurrences (11B37) Iteration theory, iterative and composite equations (39B12) Analysis of algorithms (68W40)

Abstract: We study divide-and-conquer recurrences of the form �egin{equation*} f(n) = alpha f(lfloor frac n2 floor) + �eta f(lceil frac n2 ceil) + g(n) qquad(nge2), end{equation*} with $g(n)$ and $f(1)$ given, where $$ with $$; such recurrences appear often in analysis of computer algorithms, numeration systems, combinatorial sequences, and related areas. We show that the solution satisfies always the simple emph{identity} �egin{equation*} f(n) = n^{log_2(alpha+�eta)} P(log_2n) - Q(n) end{equation*} under an optimum (iff) condition on $g(n)$. This form is not only an identity but also an asymptotic expansion because $Q(n)$ is of a smaller order. Explicit forms for the emph{continuity} of the periodic function $P$ are provided, together with a few other smoothness properties. We show how our results can be easily applied to many dozens of concrete examples collected from the literature, and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary, but leads to the strongest types of results for all examples to which our theory applies.

Recommendations

• Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications
• Divide-and-conquer recurrences -- classification of asymptotics
• Asymptotics of divide-and-conquer recurrences via iterated function systems
• Solution of a Divide-and-Conquer Maximin Recurrence
• Exact asymptotics of divide-and-conquer recurrences

Cites work

• A master theorem for discrete divide and conquer recurrences
• A Sorting Problem
• An asymptotic theory for recurrence relations based on minimization and maximization.
• Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
• Distribution of the sum-of-digits function of random integers: a survey
• Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications
• Exact solution of a minimal recurrence
• scientific article; zbMATH DE number 988836 (Why is no real title available?)
• scientific article; zbMATH DE number 3886001 (Why is no real title available?)
• scientific article; zbMATH DE number 3139051 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3705907 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 2018401 (Why is no real title available?)
• scientific article; zbMATH DE number 3271087 (Why is no real title available?)
• scientific article; zbMATH DE number 3064333 (Why is no real title available?)
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• scientific article; zbMATH DE number 7647200 (Why is no real title available?)
• Improved master theorems for divide-and-conquer recurrences
• Mellin transforms and asymptotics. The mergesort recurrence
• Mellin transforms and asymptotics: Digital sums
• Mellin transforms and asymptotics: Harmonic sums
• Power and Exponential Sums of Digital Sums Related to Binomial Coefficient Parity
• Recurrence relations based on minimization
• Regular expressions: new results and open problems
• Sur la fonction sommatoire de la fonction 'somme des chiffres'
• The Takagi function: a survey

Cited in

(3)

• Analysis of regular sequences: summatory functions and divide-and-conquer recurrences
• Periodic behavior of the minimal Colijn-Plazzotta rank for trees with a fixed number of leaves
• Periodic minimum in the count of binomial coefficients not divisible by a prime

This page was built for publication: Identities and periodic oscillations of divide-and-conquer recurrences splitting at half

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