Question about the "master theorem" of recurrences - no "$b$" term

Question

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.

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?

Answer 1

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)$

Answer 2

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).