6
$\begingroup$

While thinking about this question on a recurrence I checked out some stronger master theorems. Unfortunately, they do not seem to apply because terms

$\qquad\displaystyle T(n) = \dots + T(n-1) + \dots$

are not covered.

  • Roura [1] investigates (in the discrete case) recurrences of the form

    $\qquad\displaystyle T(n) = t_n + \sum_{1 \leq d \leq D} (w_d + r_{d,n}) \cdot T(z_d n + s_{d,n})$

    where $\sum |r_{d,n}|$ and $\sum |s_{d,n}|/n$ have to vanish for $n \to \infty$ and, sadly, $0 < z_d < 1$. I did not go through the proof, but an application to the example at hand yielded a quite clearly wrong result of $T \in \Theta(g)$, so this one does not carry over as is.

  • Akra and Bazzi [2] consider only recurrences of the form

    $\qquad\displaystyle T(n) = g(n) + \sum_{i=1}^k a_i T(\lfloor n/b_i \rfloor)$

    with $b_i \geq 2$, so above parameter choice is clearly not covered.

    Leighton [3] introduces a more general form of Akra-Bazzi for recurrences of the form

    $\qquad\displaystyle T(x) = g(x) + \sum_{i=1}^k a_iT(b_ix + h_i(x))$,

    but similarly requires that $b_i \in (0,1)$. It seems to me that existence of $p$ as solution of

    $\qquad\displaystyle \sum_{i=1}^k a_i b_i^p = 1$

    in Theorem 2 can no longer be guaranteed if there is one $b_i=1$ since all $a_i$ are positive.

  • Drmota and Szpankowski [4] look at recurrences of the form

    $\qquad\displaystyle T(n) = a_n + \sum_{j=1}^m b_jT(\lfloor p_j n + \delta_j \rfloor)$

    with $0 < p_j < 1$. The proof does not explicitly use $p_j \neq 1$. I am not too sure about the properties of several Dirichlet series (cf section 4.1) if some $p_j=1$, though.

Does any of the theorems hold if there are recursive parameters of the form $T(n-d)$? Can one be adapted to cover such cases, or are there other, more general results that do so?

To summarise, what do we know about solutions of recurrences of the form

$\qquad\displaystyle T(n) = \sum_{i \in I} a_i T(n/b_i) + \sum_{j \in J} c_j T(n-d_j) + f(n) $?


  1. An improved master theorem for divide-and-conquer recurrences by S. Roura (1997)
  2. On the solution of linear recurrence equations by M. Akra and L. Bazzi (1998)
  3. Notes on Better Master Theorems for Divide-and-Conquer Recurrences by T. Leighton (1996)
  4. A master theorem for discrete divide and conquer recurrences by M. Drmota and W. Szpankowski. (2011)
$\endgroup$
  • $\begingroup$ I realise that this is a candidate for Theoretical Computer Science but I figured I'd try here first. $\endgroup$ – Raphael Nov 12 '13 at 14:28
  • $\begingroup$ What are you looking for? Existence theorems that guarantee solutions, or solutions in closed form, or the asymptotic behavior of the solution? $\endgroup$ – Andrej Bauer Sep 11 '14 at 14:07
  • $\begingroup$ Ah, asymptotic behavior, judging from your first example. Correct? $\endgroup$ – Andrej Bauer Sep 11 '14 at 14:08
  • $\begingroup$ @AndrejBauer In the context of algorithm analysis, I'd say we can safely assume the existence of solutions; then, I'd not expect much beyond asymptotics. So, yes, asymptotics are fine. $\endgroup$ – Raphael Sep 11 '14 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.