Solving divide & conquer reccurences if the split-ratio depends on $n$

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.

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.

• 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.

• 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 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$.

StackExchange Computer Science Q#10088, answer score: 6