20
$\begingroup$

Is there a general method to solve the recurrence of the form:

$T(n) = T(n-n^c) + T(n^c) + f(n)$

for $c < 1$, or more generally

$T(n) = T(n-g(n)) + T(r(n)) + f(n)$

where $g(n),r(n)$ are some sub-linear functions of $n$.

Update: I have gone through the links the provided below and also sifted through all the recurrence relations in Jeff Erickson's notes. This form of the recurrence is not discussed anywhere. Akkra-Bazi method applies only when the split is fractional. Any poignant reference will be apprieciated.

$\endgroup$
  • 2
    $\begingroup$ Try generating functions. $\endgroup$ – mrk Feb 25 '13 at 17:00
  • 1
    $\begingroup$ Does the Akra-Bazzi method apply? It only gives $O(\cdot)$ estimates, but that might be enough. $\endgroup$ – vonbrand Feb 25 '13 at 17:02
  • 4
    $\begingroup$ Since you did not include much of an attempt to solve your problem on your own, we have litte to work with. Let me direct you towards our reference questions which cover problems similar to yours in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. $\endgroup$ – Raphael Feb 25 '13 at 17:07
  • 1
    $\begingroup$ Check out Tom Leighton's handouts on "Notes on better master theorems for divide-and-conquer recurrences", they are available on the 'net. Perhaps you can adapt the proof of Akra-Bazzi there to your case. $\endgroup$ – vonbrand Mar 7 '13 at 18:48
  • 1
    $\begingroup$ @EngrStudent Generating functions were proposed in the very first comment. :) $\endgroup$ – Raphael Nov 15 '16 at 10:25
6
$\begingroup$

Let's say you have a recurrence $$ T(n) = \begin{cases} T(n - n^c) + T(n^c) + f(n) & \text{n > 2} \\ 1 & \text{otherwise} \end{cases} $$ that ranges over positive reals.

What can we do with this function? Well, not a lot unless we superimpose certain structures upon it. I came from a numerical analysis background, which is paved with numerical recipes that somehow works even when the underlying problem is either not smooth enough (doesn't matter, let's still throw Newton's method at its divided differences) or too complicated to analyze (sort of like this problem). My gut reaction towards these problems is to make some handwaved assumption, cross our fingers, and hope for the best. In this case, it seems to give relatively good bounds.

In particular, I want to make two major assumptions. One of these assumptions is more or less baseless, but we won't get very far without it. The other has a somewhat nice visual intuition that you can hopefully grok, but it is still more handwavy than anything else.

  1. I will assume that $T(n)$ is "smooth-ish". It's fairly easy to see that $T(n)$ is not everywhere differentiable. In fact, it isn't even continuous, since for $f(n) = \log(n)$ and $c = \frac{1}{2}$, $\lim_{n \to 2^-} T(n) = 1$ and $\lim_{n \to 2^+} T(n) = 2 + \ln 2$. Therefore, given the iterated maps generated by $n \mapsto \sqrt{n}$ or $n \mapsto n - \sqrt{n}$, $T(n)$ will contain a discontinuity at $n$ if its iteration tree contains $2$ somewhere in its trajectory. That is a lot of discontinuities, it might even give Dirichlet's function a run for its money. If we're getting to the point where we are comparing a function's behaviors to that of the prototypical example of a nowhere-continuous function, isn't it laughable to try to claim that it is "smooth-ish"? Well, it turns out that in practice, the effects of these discontinuities asymptotically diminishes, to the point that your graph looks almost smooth when $n$ tends towards infinity! Therefore, I propose that we put down our pitchforks and just look the other-way in this circumstance. In particular, I will assume that at any point of interest $n$ that is sufficiently far away from the origin, $T(n)$ is differentiable, or at least approximately differentiable around some neighborhood.
  2. I will also assume an even stronger stance of smoothness when $n$ is sufficiently far away. Suppose that $\alpha(n)$ is some sublinear function such that $n > \alpha(n)$ (for example $n^c$), then the derivative $T'(\xi \in (n - \alpha(n), n)$ does not vary significantly when $\alpha(n)$ is slow enough. Intuitively, as $n$ gets larger, the relative size of the neighborhood $(n - \alpha(n), n)$ decreases (since its size is just $\alpha(n)$, which grows much much slower than $n$ does). Eventually, the size of this neighborhood becomes so insignificant (relative to $n$) that the rate of change of $T(n)$ within this neighborhood no longer changes all that dramatically.

Now, both of these properties are assumed, and I have zero idea how to go about actually proving either in any rigorous way. But like I said before, let's cross our fingers and hope for the best.

Let's start with the recurrence relation: \begin{align*} T(n) &= T(n - n^c) + T(n^c) + f(n) \\ T(n) - T(n - n^c) &= T(n^c) + f(n) \\ n^c\frac{T(n) - T(n-n^c)}{n^c} &= T(n^c) + f(n) \end{align*} Now, I'll assume that $T$ is smooth enough on the interval between $n - n^c$ and $n$. Appealing to one of our classical analytic tools, the mean-value-theorem, gives us $$ \frac{T(n) - T(n-n^c)}{n^c} = T'(\xi \in (n - n^c, n)). $$ Furthermore, when $n$ is sufficiently large, we assume that $T'(\xi)$ is approximately the same throughout this interval, and hence takes the value of any of the finite differences within this interval as well. This then means that $$ T'(\xi) \approx \frac{T(n) - T(n - \epsilon)}{\epsilon} ~~~~ \epsilon < n^c $$ In particular, take $\epsilon = 1$ to get a one-step divided difference approximation \begin{align*} n^c (T(n) - T(n-1)) &\approx T(n^c) + f(n) \\ T(n) - T(n-1) &\approx \frac{T(n^c) + f(n)}{n^c} \\ \end{align*} We can telescope this out to get $$ T(n) \approx \sum_k^n \frac{T(k^c)}{k^c} + \sum_k^n \frac{f(k)}{k^c} $$

Perturbing $T(n)$ reveals that $T(n)$ has two asymptotic phases, depending on the asymptotic nature of $f(z)$.

When $f(n) = o(n^c)$ ($f$ is faster than $n^c$), then the right sum dominates, and we have $T(n) = \Theta\left(\sum\limits_k^n \frac{f(k)}{k^c}\right)$ which can often be approximated with the integral $\int\limits^n \frac{f(x)}{x^c} dx$.

When $f(n) = \omega(n^c)$, then the left sum dominates the right. Here, we have to analyze the sum $$ \left(\sum_k^n \frac{T(k^c)}{k^c}\right) + F_c(n) $$ where $F_c(n) = \int\limits^n \frac{f(x)}{x^c}dx$.

By virtue of the smoothness argument, we can once again look at this as a left-anchored Riemann sum, approximating the integral $\int_n \frac{T(x^c)}{x^c} dx$. Applying a similar mean-value-theorem over the integral gives $$ \sum_k \frac{T(k^c)}{k^c} \approx \int^n \frac{f(x^c)}{x^c} dx = n\frac{T(\xi < n^c)}{\xi^c} $$ We can just go ahead and approximate this by $n\frac{T(n^c)}{n^c}$, which gives the approximation \begin{equation} T(n) \le n M \frac{T(n^c)}{n^c} + F_c(n) \end{equation} for some constant $M$ that bounds the series.

Now, suppose that we have the iterated sequence $(n, n^c, n^{c^2}, n^{c^3}, \dots, n^{c^k})$ where $n^{c^k} < 2$, then we can use this sequence to telescope the above inequality to get: $$\label{eqn:meh} T(n) \le n \left(\sum_i^{k-1} \frac{M^i}{n^{c^i}}F_c(n^{c^i}) + \frac{M^k}{n^{c^k}}\right) \tag{*} $$ Once again, we can bound the $F_c(n^{c^i})$ term by some constant to find that $$ T(n) = O\left(F_c(n) + n F_c(n^c) \left(M n^{-c} + M^2 n^{-c^2} + \dots + M^k n^{-c^k}\right)\right) $$ where $k = \log_c\left(\frac{\log(2)}{\log(n)}\right)$. Simplifying a bit and coalescing some of the $Mn^{-c}$ terms together (in particular, we know that $n^{-c^k}$ is a constant), we get $$ T(n) = O\left(n k F_c(n) M^{k} \right) $$

However, this bound is relatively loose, and you should refer to $(\ref{eqn:meh})$ whenever possible.

Be aware that in no way is this rigorous. I have not provided any support that this ought to work beyond some clumsy approximations. Nevertheless, if you just need a quick asymptotic guess for the sake of informal analysis, then you can actually see that this scheme works well (for large enough values of $n$, usually $n > 10$ suffices) in practice.

Anyways, for all of the choices of $c$ and $f$ that I've tried, the following computation \begin{align*} \hat T(n) &= n \sum_k^{\log_c \log_n 2} \frac{M^k}{n^{c^k}} F(n^{c^k}) \\ F(n) &= \sum_k^n \frac{f(k)}{k^c} \end{align*} where $$ M \approx \frac{\sum_k \frac{T(k^c)}{k^c}}{n \frac{T(n^c)}{n^c}} $$ seems to give good approximations. This technique also generalizes to recurrences of the form $$ T(n) = T(n - \alpha(n)) + T(\beta(n)) + f(n) $$ which can be approximated with \begin{align*} \hat T(n) &= n \sum_k^{\#_\beta(n)} \frac{M^k}{\alpha^k(n)} F(\beta^k(n)) \\ F(n) &= \sum_k^n \frac{f(k)}{\alpha(k)} \end{align*} where $\alpha^k(n) = \alpha(\stackrel{k}{\cdots}(\alpha(n)))$ and $\#_\beta(n)$ denotes the number of elements of the sequence $n, \beta(n), \beta(\beta(n)), \dots, \beta^{\#_\beta(n)}(n)$ such that the last term is between $1$ and $2$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.