Asymptotic approximation of a recurrence relation (Akra-Bazzi doesn't seem to apply) Suppose an algorithm has a runtime recurrence relation:

$   T(n) = \left\{
     \begin{array}{lr}
       g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) &amp; : n \ge n_0\\
       f(n) &amp; : n &lt; n_0
     \end{array}
   \right.
$  

for some constant $0 &lt; \delta &lt; 1$. Assume that $g$ is polynomial in $n$, perhaps quadratic. Most likely, $f$ will be exponential in $n$.

How would one go about analyzing the runtime ($\Theta$ would be excellent)? The master theorem and the more general Akra-Bazzi method do not seem to apply.
One possible approach might be by analogy to differential equations.  Let $T'(n) = T(n)-T(n-1)$.  Here $T'(n)$ is a discrete analog of the first derivative of $T(n)$.  We get the following relationship:
$$T'(n) = T(\lfloor \delta n \rfloor) + g(n).$$
The continuous analog of this is the differential equation
$$t'(x) = t(\delta x) + g(x),$$
or, if you prefer to see it written differently:
$${d \over dx} t(x) = t(\delta x) + g(x).$$
That's a differential equation.

Now you could try to solve the differential equation for the continuous function $t(x)$, then hypothesize that a similar function will be the solution to your original recurrence relation, and try to prove your hypothesis.  At least, this is one general approach you could follow.

I've forgotten everything I once knew about differential equations, so I don't know the solution that differential equation, but maybe you will be able to solve it by reviewing all the techniques for solving differential equations.