3
$\begingroup$

I'm using the master theorem to find the asymptotic run time of recurrences.

For example, for a $T(n) = 4 T(n/5) + n^1$

I find that $T(n)$ is $\Theta(n^1)$, or, simply, constant time, via the set of rules presented in the master theorem.

what I know about the master theorem

My question is - what if the $n$ term is reduced by a constant factor instead of divided.

For the recurrence:

$$T(n) = 9T(n-3) + n^7$$

Can we ignore the "$-3$" term entirely and take our "$b$" as $1$?

How can I apply the master theorem principles?

$\endgroup$
2
$\begingroup$

No you can't ignore the -3, actually this case is a lot worse than the "normal" case.

For instance imagine $T(n)=2T(n-1)$, then it means $T(n)=\Theta(2^n)$, because you have to use the recurrence relation $n$ times instead of $log_b(n)$ times.

In your case it will be the same: you have $T(n)=\Theta(9^{n/3})=\Theta((\sqrt[3]9)^n)$

$\endgroup$
2
  • $\begingroup$ Wow - thanks, and dang... how would you suggest solving such a recurrence to find runtime? Without the master theorem... I'm not sure which methods to employ. $\endgroup$ – PinkElephantsOnParade Jan 22 '14 at 1:09
  • $\begingroup$ it is the classical recurrence relation : $u_{n+1}=au_n+b$, that you can solve via fixpoints... $\endgroup$ – Denis Feb 5 '14 at 11:09
1
$\begingroup$

Unfortunately, the Master Theorem doesn't apply to recurrences like the one you stated. All is not lost, though. Let's look at what happens in general, to see if we can come up with a master theorem of our own for the recurrence relation $$ T(n)=aT(n-1)+f(n) $$ (we could do this for $T(n-b)$ but that would complicate what follows).

Let's assume that we know $T(0)$. Start with $$ T(n)=aT(n-1)+f(n) $$ and use the recurrence repeatedly on the $T()$s on the left, aiming to drive them to the known value $T(0)$ $$\begin{align} T(n) &= a\color{red}{T(n-1)}+f(n)\\ &= a\color{red}{(aT(n-2)+f(n-1))} + f(n) \\ &= \quad a^2T(n-2)+af(n-1)+f(n)&\text{expand again}\\ &=a^2(aT(n-3)+f(n-2))+af(n-1)+f(n)\\ &= \quad a^3T(n-3) + a^2f(n-2)+af(n-1)+f(n)&\text{expand again}\\ &=a^3(aT(n-4)+f(n-3)) + a^2f(n-2)+af(n-1)+f(n)\\ &= \quad a^4T(n-4)+ a^3f(n-3) + a^2f(n-2)+af(n-1)+f(n)\\ \end{align}$$ and the pattern in general appears to be $$ T(n) = a^jT(n-j)+\sum_{k=0}^{j-1}a^kf(n-k) $$ We want to drive the $T(n-j)$ term down so something we know, namely $T(0)$, so let $j=n$. Doing this we have $$\begin{align} T(n) &= a^nT(n-j)+\sum_{k=0}^{n-1}a^kf(n-k)\\ &= a^nT(0)+\sum_{k=0}^{n-1}a^kf(n-k) \end{align}$$ So we have a closed form solution to the original recurrence relation. In particular, if we're lucky enough to have $T(0)=f(0)$ we just have $$ T(n)=\sum_{k=0}^na^kf(n-k) $$ Now the sum part might be really ugly or not, depending on what $f$ is.

Example 1. Let $f(n)=1, a=3$ so we have $T(n)= 3T(n-1)+1$ and with $T(0)=f(0)=1$ we have $$ T(n)=\sum_{k=0}^n3^k\cdot 1 = \frac{3^{n+1}-1}{3-1}=\frac{1}{2}(3^{n+1}-1) $$

Example 2. Let $f(n)=n, a=2$ so we have $T(n)= 2T(n-1)+n$ and with $T(0)=f(0)=0$ we have $$ T(n)=\sum_{k=0}^n2^k(n-k) $$ and with a fair amount of work we can find that $$ T(n) = 2 + (n-1)2^{n+1} $$ I suspect that the reason this isn't as well-known as the other Master Theorem is that it just doesn't lead to a nice answer in most cases (though some texts do mention it).

$\endgroup$

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.