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

Show simple item record

dc.contributor.author Coronado, Tomas M.
dc.contributor.author Mir, A.
dc.contributor.author Rosselló, F.
dc.date.accessioned 2024-02-07T07:34:35Z
dc.date.available 2024-02-07T07:34:35Z
dc.identifier.uri http://hdl.handle.net/11201/164593
dc.description.abstract Divide-and-conquer dividing by a half recurrences, of the form x_n = a x_{⌈n/2⌉}+ a x_{⌊n/2⌋}+p(n), n>=2, appear in many areas of applied mathematics, from the analysis of algorithms to the optimization of phylogenetic balance indices. These equations are usually 'solved' by means of a Master Theorem that provides a bound for the growing order of x_n, but not the solution's explicit expression. In this paper we give a finite explicit expression for this solution, in terms of the binary decomposition of n, when the independent term p(n) is a polynomial in ⌈n/2⌉ and ⌊n/2⌋. As an application, we obtain explicit formulas for several sequences of interest in phylogenetics, combinatorics, and computer science, for which no such formulas were known so far: for instance, for the Total Cophenetic index and the rooted Quartet index of the maximally balanced bifurcating phylogenetic trees with n leaves, and the sum of the bitwise AND operator applied to pairs of complementary numbers up to n.
dc.format application/pdf
dc.relation.isformatof Reproducció del document publicat a: https://doi.org/10.1371/journal.pone.0274448
dc.relation.ispartof Plos One, 2022, vol. 17, num. 11, p. 1-37
dc.rights cc-by (c) Coronado, Tomas M. et al., 2022
dc.rights.uri https://creativecommons.org/licenses/by/4.0/
dc.subject.classification 51 - Matemàtiques
dc.subject.classification 004 - Informàtica
dc.subject.other 51 - Mathematics
dc.subject.other 004 - Computer Science and Technology. Computing. Data processing
dc.title Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term
dc.type info:eu-repo/semantics/article
dc.type info:eu-repo/semantics/publishedVersion
dc.date.updated 2024-02-07T07:34:36Z
dc.subject.keywords Recurrence
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.identifier.doi https://doi.org/10.1371/journal.pone.0274448

Files in this item

The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record

cc-by (c) Coronado, Tomas M. et al., 2022 Except where otherwise noted, this item's license is described as cc-by (c) Coronado, Tomas M. et al., 2022

Search Repository

Advanced Search


My Account