Identities and periodic oscillations of divide-and-conquer recurrences splitting at half
October 20, 2022 Β· Declared Dead Β· π arXiv.org
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Hsien-Kuei Hwang, Svante Janson, Tsung-Hsi Tsai
arXiv ID
2210.10968
Category
cs.DS: Data Structures & Algorithms
Cross-listed
math.CO
Citations
1
Venue
arXiv.org
Last Checked
4 months ago
Abstract
We study divide-and-conquer recurrences of the form \begin{equation*} f(n) = Ξ±f(\lfloor \tfrac n2\rfloor) + Ξ²f(\lceil \tfrac n2\rceil) + g(n) \qquad(n\ge2), \end{equation*} with $g(n)$ and $f(1)$ given, where $Ξ±,Ξ²\ge0$ with $Ξ±+Ξ²>0$; 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} \begin{equation*} f(n) = n^{\log_2(Ξ±+Ξ²)} 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.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
π Similar Papers
In the same crypt β Data Structures & Algorithms
π
π
The Cartographer
R.I.P.
π»
Ghosted
Route Planning in Transportation Networks
R.I.P.
π»
Ghosted
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
R.I.P.
π»
Ghosted
Hierarchical Clustering: Objective Functions and Algorithms
R.I.P.
π»
Ghosted
Graph Isomorphism in Quasipolynomial Time
π
π
The Cartographer
Simulation optimization: A review of algorithms and applications
Died the same way β π» Ghosted
R.I.P.
π»
Ghosted
Federated Learning: Strategies for Improving Communication Efficiency
R.I.P.
π»
Ghosted
In-Datacenter Performance Analysis of a Tensor Processing Unit
R.I.P.
π»
Ghosted
Deep Convolutional Neural Networks for Computer-Aided Detection: CNN Architectures, Dataset Characteristics and Transfer Learning
R.I.P.
π»
Ghosted