When applying the master theorem, how to decide on case 1, 2, or 3?

Question

When you are given a relation, such as $$T(n)=8T\Big(\frac{n}{2}\Big)+160n,$$

what are the logical steps to consider when deciding whether to apply case 1, 2, or 3? Or do you have to apply all 3 and then choose the best result?

Answer 1

No, only one case can apply at a time. It's also easy to make up recursions, even realistic ones, that don't fit the framework at all.

The basic idea of the master theorem is to compare the growth rate of the homogeneous recurrence and the inhomogenous part. If the homogeneous recurrence is way bigger, then the inhomogenous solution behaves like the homogeneous solution. If the inhomogeneous part is way bigger, then the inhomogeneous solution behaves just like the inhomogeneous part. If they're both right around the same growth rate, then there is a tendency toward "feedback", so that the inhomogeneous solution is bigger than either the inhomogeneous part or the homogeneous solution...although the master theorem only handles a very specific case of this*.

To be more specific, the homogeneous recurrence wants to grow as $n^{\log_b(a)}$ (in your example, $b=2,a=8$). If the homogeneous part is way smaller than that, then the behavior of $T(n)$ is controlled by the homogeneous solution, and so $T(n)=\Theta(n^{\log_b(a)})$. We quantify "way smaller" by saying that $f(n)=O(n^{\log_b(a)-\varepsilon})$ for some $\varepsilon>0$. This is case 1.

If the inhomogenous part is way bigger than the solution to the homogeneous problem, then $T(n)=\Theta(f(n))$. We quantify "way bigger" by saying that $f(n)=\Omega(n^{\log_b(a)+\varepsilon})$ for some $\varepsilon>0$. This is case 3. (This case actually requires a bit more than that, but the auxiliary "regularity condition" is usually satisfied.)

If $f(n)$ is behaving the same as $n^{\log_b(a)}$, or is just bigger by a factor behaving like $\log(n)^k$ for some $k \geq 0$, then the inhomogeneous part and the homogeneous part "feedback on each other", causing the solution to be bigger than either the inhomogeneous or homogeneous parts. This is case 2, which leads to $T(n)=\Theta(n^{\log_b(a)} \log(n)^{k+1})$.

* Side remark: the Akra-Bazzi method is a generalization of the master theorem. One of several things that it does better is handling the case where $f(n)/n^{\log_b(a)}$ is neither $\Omega(n^{\varepsilon})$ nor $O(n^{-\varepsilon})$ for any $\varepsilon>0$.

Answer 2

As a suggestion, do not rely on recipes, just look carefully at the recurrence you are trying to solve. It is pretty simple to eliminate the inhomogeneous part by setting $T(n)=A(n)-kn$ for a suitable constant $k$:

$$ A(n)-kn = 8 A\left(\frac{n}{2}\right) - 4kn + 160 n $$ simplifies into $$ A(n) = 8 A\left(\frac{n}{2}\right) $$ by picking $k=\frac{160}{3}$. The least relation implies $A(n)=\Theta\left(8^{\log_2 n}\right) = \Theta(n^3) $,
hence $T(n)=\Theta(n^3)$.