Divide-and-conquer recurrences -- classification of asymptotics
This paper investigates the asymptotic behaviour of the sequence \(\{f_n\}\) defined by means of a divide-and-conquer recursion \[ [2^n-(a_1+a_0)]f_n=a_1\sum_{k=0}^{n-1}\binom{n}{k}\alpha^{n- k}f_k+b_1\beta^n,\quad n>l , \tag{1} \] where \(\alpha ,\beta >0, a_0,a_1\neq 0,b_1\in\mathbb R\) are given parameters and \(f_0,f_1,\dots ,f_l\) are the initial values. It is known that some particular cases of this recurrence relation admit a very different asymptotic behaviour of solutions. The main result of this paper gives a complete list of all possible types of the asymptotic behaviour of general recurrences defined by use of (1). The sign of \(\triangle =2\alpha -\beta\) turns out to be the key assumption of this statement. Put \(\rho =\log_2a_1\). If \(\triangle >0\), then \[ \alpha^{-n}f_n=n^{\rho}K(\log _2n)+O(n^{\rho -1}) , \tag{2} \] where \(K\) is an analytic and periodic function with period 1. If \(\triangle <0\), then \[ \left (\frac{\beta}{2}\right)^{-n}f_n=b_1+O(n^{-1}) . \] If \(\triangle =0\), then some additional requirements on the value of \(\rho\) are necessary to prove the modifications of formula (2). The method of the proof is based on considering the exponential generating function \(f(z)\) of the sequence \(\{f_n\}\) given by \[ f(z)=\sum_{n=0}^{\infty}\frac{f_n}{n!}z^n . \] It is shown that \(f(z)\) is an entire solution of the functional equation \[ f(2z)=(a_1\text{ e}^{\alpha z}+a_0)f(z)+b_1\text{ e}^{\beta z}+b_0(z) \] and its asymptotic behaviour determines the asymptotics of \(f_n\).
- Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications
- Asymptotics of divide-and-conquer recurrences via iterated function systems
- An asymptotic theory for recurrence relations based on minimization and maximization.
- Exact asymptotics of divide-and-conquer recurrences
- Solution of a Divide-and-Conquer Maximin Recurrence
- An asymptotic theory for recurrence relations based on minimization and maximization.
- Asymptotics of some convolutional recurrences
- Asymptotic analysis of binomial recurrences
- Asymptotic limits of a new type of maximization recurrence with an application to bioinformatics
- Asymptotics of divide-and-conquer recurrences via iterated function systems
- Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated
- Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications
- Exact asymptotics of divide-and-conquer recurrences
- An elementary approach to some analytic asymptotics
- Rational divide-and-conquer relations
- scientific article; zbMATH DE number 3073237 (Why is no real title available?)
- Identities and periodic oscillations of divide-and-conquer recurrences splitting at half
This page was built for publication: Divide-and-conquer recurrences -- classification of asymptotics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1592813)
