Back to Search
Start Over
Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term.
- Source :
-
PLoS ONE . 11/17/2022, Vol. 17 Issue 11, p1-37. 37p. - Publication Year :
- 2022
-
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 xn, 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYNOMIALS
*COMPUTER science
*MATHEMATICAL optimization
*COMBINATORICS
*PHYLOGENY
Subjects
Details
- Language :
- English
- ISSN :
- 19326203
- Volume :
- 17
- Issue :
- 11
- Database :
- Academic Search Index
- Journal :
- PLoS ONE
- Publication Type :
- Academic Journal
- Accession number :
- 160281869
- Full Text :
- https://doi.org/10.1371/journal.pone.0274448