Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?

Question

To make my question more concrete, here is an example I am stuck on.

I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$ is $\Theta(n^3\log(n))$, so both $O(n^3\log(n))$ and $\Omega(n^3 \log(n))$.

We know $T(n) = \Theta(n^3 \log(n)) \Leftrightarrow \exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.

Given that I assume the proof should go somewhat as follows:

To show: $\exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$

To do this we can use strong induction.

Let $P(n)$ be $c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.

Take $n$ to be an arbitrary natural number.

Induction hypothesis: $P(1),P(2),...,P(n-1)$. And notably, $P(\frac{n}{2})$.

It seems fairly straight forward to show the right-hand side of $P(n)$, that is that $\forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.

It follows that (taking $\log$ to be in base $2$):

$$ \begin{align*} P(\frac{n}{2}) &\Leftrightarrow T(\frac{n}{2}) \leq c_2 (\frac{n}{2})^3\log(\frac{n}{2}) \\ &\Leftrightarrow 8T(\frac{n}{2}) + n^3 \leq 8c_2 (\frac{n}{2})^3 \log(\frac{n}{2}) + n^3 \\ & \Leftrightarrow T(n) \leq 8c_2\frac{n^3}{8}(\log(n) - log(2)) + n^3 \\ & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3log(2) \\ & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3 \leq c_2n^3\log(n) \ \text{ (if $c_2 \geq 1$)} \end{align*} $$

So we have $P(n)$.

And as such $\exists c_2, n_0 > 0: \forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.

My problem:

So we have shown that $T(n) = O(n^3 \log (n))$ but not yet that $T(n) = \Omega(n^3 \log (n))$ which is also required to have $T(n) = \Theta(n^3 \log(n))$.

And that is what I am not sure how to go about showing — the left-hand side of $P(n)$, that is that given $P(\frac{n}{2})$, we have $c_2 n^3 \log(n) \leq T(n)$.

Can someone provide some insight into how to approach this?

Answer 1

You can prove precise equality for your recurrence. I'm going to assume the base case:

$$T(n) = \begin{cases} 8 & n = 2\\ 8T\left(\tfrac{n}{2}\right) + n^3 & n > 2\\ \end{cases}$$

Claim: $T(n) = n^3 \log_2 n$

Base Case ($n = 2$): $T(2) = 8 = 2^3 \log_2 2 = 8$

Inductive Case ($n > 2$):

$$\begin{align*} T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\ & = 8\left(\tfrac{n^3}{8} \log_2 \tfrac{n}{2}\right) + n^3\\ & = n^3 \log_2 \tfrac{n}{2} + n^3\\ & = n^3 \log_2 n - n^3 \log_2 2 + n^3\\ & = n^3 \log_2 n - n^3 + n^3\\ & = n^3 \log_2 n & \square \end{align*}$$

Thus $T(n) = n^3 \log_2 n \implies T(n) = O(n^3 \log n)$. No need to mess with lower or upper bounds.

---

However, in general this equality might not be the correct solution. Sometimes you will need to add lower order terms to get the equality or inequality to hold. A general approach to determine the lower order terms is as follows:

If we have:

$$T(n) = \begin{cases} f(b) & n = b\\ aT(n/b) + f(n) & n > b \end{cases}$$

We first assume $n = b^k$ for some $k$. Next we can turn this into a summation:

$$\begin{align*} T(n) & = aT(n/b) + f(n)\\ & = a(aT(n/b^2) + f(n/b)) + f(n)\\ & = a^2T(n/b^2) + af(n/b) + f(n)\\ & \vdots\\ & = \sum_{i = 0}^{\log_b n - 1} a^{i} f\left( \frac{n}{b^i}\right) \end{align*}$$

Then if you can find a closed form for this sum, we can easily prove equality by induction (e.g. substitution method) with proper constants. Here is your example again:

$$\begin{align*} T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\ & = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \left( \frac{n}{2^i}\right)^3\\ & = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \frac{n^3}{2^{3i}}\\ & = \sum_{i = 0}^{\log_2 n - 1} n^3\\ & = n^3 \log_2 n\\ \end{align*}$$

Now you can go ahead and use this in your substitution method and you should not have any issues.

---

Feel free to try the same method with a trickier example:

$$T(n) = \begin{cases} 12 & n = 3\\ 5T\left(\tfrac{n}{3}\right) + n^2 + n & n > 3\\ \end{cases}$$

Answer 2

You can prove a recurrence of the form $$aT(n/b) + f(n)$$ if the constraints for master theorem hold. A bad value for f(n) might invalidate that.