Suppose an algorithm has a runtime recurrence relation:

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

for some constant $0 < \delta < 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.

  • $\begingroup$ Finding good lower bound is easy but finding good upper bound is hard, but roughly speaking seems to be close to $T(n) = a\cdot T(n/a) + g(n)$. $\endgroup$ – user742 Sep 16 '13 at 21:02
  • 1
    $\begingroup$ If you are at still looking for an answer you should check Graham, Knuth, and Patashnik, "Concrete Mathematics". $\endgroup$ – Kaveh Nov 13 '13 at 6:41
  • $\begingroup$ Assuming that $n_0$ is constant, we don't need any assumptions on $f$, or do we? $\endgroup$ – Raphael Nov 13 '13 at 21:55
  • $\begingroup$ The parameter $n_0$ may be instance-specific. It would be nice to see how the runtime depends on $n_0$. $\endgroup$ – Austin Buchanan Nov 13 '13 at 21:59
  • 1
    $\begingroup$ I asked a related question that, so far, has not brought forth any general theorem for recurrences of this kind. $\endgroup$ – Raphael Dec 9 '14 at 18:03

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.

  • $\begingroup$ Donald J Newman seems to have used this technique often, with great results. $\endgroup$ – Aryabhata Nov 12 '13 at 22:26
  • $\begingroup$ Without looking further. It is not easy to solve that differential equation. I am not too convinced that it has a closed form solution after trying a few basic form for $t(x)$. $\endgroup$ – InformedA Dec 10 '14 at 18:26

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.