10
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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, 2014 at 18:03

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Donald J Newman seems to have used this technique often, with great results. $\endgroup$
    – Aryabhata
    Nov 12, 2013 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, 2014 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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