1
$\begingroup$

I'm trying to solve a recurrence problem using substitution method:

Given the following recurrence equation:
$ T(n) = \begin{cases} 3 &n = 0 \\ 3T(\frac{n}{5}) + T(\frac{n}{6}) + n&n > 0 \end{cases} $
provide a tight asymptotic bound for the solution

I've been trying to understand how the recursion tree is made, but I'm not sure that's the smartest way to get the hypothesis to apply the substitution method.

In fact, I looked at the solution provided with the exercise and the first statement is just $T(n) = \Theta(n)$ (the demonstration of this is made right after)
I just don't understand how to get the proper hypothesis, because in my mind, this should have been something like $T(n) = \Theta(n\log n)$.

$\endgroup$

1 Answer 1

1
$\begingroup$

A simple rule to get the hypothesis.

Assume $T(n)\ge0$ for all $n$. Suppose the recurrence relation is $$T(n) = a_1T(b_1n) + a_2T(b_2n) + cn$$ where $a_i, b_i, c$ are constants, $a_i\ge0$ and $0\lt b_i\lt 1$ for all $i$, $c>0$.

The asymptotic approximation depends on the value $a_1b_1+a_2b_2$.

  • If $a_1b_1+a_2b_2<1$, then $T(n)=\Theta(n)$;
  • If $a_1b_1+a_2b_2=1$, then $T(n)=\Theta(n\log n)$;
  • If $a_1b_1+a_2b_2>1$, then $T(n)=\Theta(n^p)$ for some $p>1$.

Some examples

Recurrence relation $a_1b_1$ + $a_2b_2$ $T(n)$
$T(n)=2T(n/2)+n$ $2\times\frac12$ = $1$ $\ \ \ $($a_2=0$) $\Theta(n\log n)$
$T(n)=T(2n/3)+2T(n/6)+5n$ $\frac23+$ $2\times$ $\frac16=$ $1$ $\Theta(n\log n)$
$T(n)= 3T(\frac{n}{5}) + T(\frac{n}{6}) + 3n$ $3\times\frac15$ + $\frac16$ = $\frac{23}{30}<1$ $\Theta(n)$
$T(n)= 3T(\frac{n}{5}) + 3T(\frac{n}{6}) + \frac n7$ $3\times\frac15$ + $3\times\frac36$ = $\frac{11}{10}>1$ $\Theta(n^p)$ for some $p>1$

What about more general situations?

The simple rule above should be sufficient for most of the basic exercises or tests in an introductory course.

The rule stays the same basically when there are more terms like $af(bn)$ in the recurrence relation. Or $cn$ is not changed much, such as $cn+d$ for some constant $d$ or $cn+\log n$.

For more general situations, you can take a look at the Akra–Bazzi method. It is also explained here. You can find how the exponent $p$ in the case of $a_1b_1+a_2b_2>1$ is defined.

$\endgroup$
2
  • $\begingroup$ Exercise. Prove the simple rule using substitution method. The first two cases are not difficult. The last case needs calculus. $\endgroup$
    – John L.
    Apr 2, 2022 at 19:19
  • $\begingroup$ Thank you so much! This is exactly what I was looking for. You put a lot of effort into this answer, I am infinitely grateful. Have a great day! $\endgroup$ Apr 3, 2022 at 11:59

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.