REVIEW
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term
read the original abstract
Divide-and-conquer dividing by a half recurrences, of the form $x_n =a\cdot x_{\left\lceil{n}/{2}\right\rceil}+a\cdot x_{\left\lfloor{n}/{2}\right\rfloor}+p(n)$, $n\geq 2$, appear in many areas of applied mathematics, from the analysis of algorithms to the optimization of phylogenetic balance indices. The Master Theorems that solve these equations do not provide the solution's explicit expression, only its big-$\Theta$ order of growth. In this paper we give an explicit expression (in terms of the binary decomposition of $n$) for the solution $x_n$ of a recurrence of this form, with given initial condition $x_1$, when the independent term $p(n)$ is a polynomial in $\lceil{n}/{2}\rceil$ and $\lfloor{n}/{2}\rfloor$.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.