[Math] Question about the “master theorem” of recurrences – no “$b$” term

asymptoticsproblem solvingrecurrence-relations

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?

Best Answer

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