Pith. sign in

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

arxiv 2111.12313 v1 pith:OTSRQ22C submitted 2021-11-24 cs.DM math.COq-bio.PE

Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term

classification cs.DM math.COq-bio.PE
keywords explicitsolutioncdotdivide-and-conquerdividingexpressionformhalf
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
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.