Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

Question

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently:

$$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$

Prove that for each $n\in\mathbb{N}_0$: $T(n) \leq 8n^2$

How can I prove such statement? I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach. Any help appreciated

Answer 1

You cannot use master Theorem (at least not as a black-box) as it only provides an asymptotic bound on the growth of $T(n)$, while you're interested in bounding the multiplicative constant too.

You can prove an upper bound your to your recurrence by induction on $n$.

The case $n=0$ is trivial as $T(0) = 0 = 8n^2$.

For $n \ge 1$ you have (notice that $\lfloor n/2 \rfloor < n$): $$ T(n) = 3T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + 2n^2 \le 3 \cdot 8\left(\left\lfloor \frac{n}{2} \right\rfloor\right)^2 + 2n^2 \le \frac{24 n^2}{4} + 2n^2 = 8n^2. $$

Edit: this is essentially the same as Apass.Jack's answer :)

Answer 2

I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach.

You are correct. While the master theorem can yield asymptotically tight bounds, the question asks you to prove an exact inequality, $T(n) \leq 8n^2$ for all for $n\in\mathbb{N}_0$.

Since this is a proposition on natural numbers, we should use mathematical induction. Because $T(n)$ is related to $T(\lfloor n/2\rfloor)$, we will use strong induction.

Base case. $n=0$: $T(0)=0\le 8\cdot0^2$.

Inductive step. Assume for all $k < n$, prove for $n >0$:

$$T(n)=3T(\lfloor{n/2}\rfloor) + 2n^2\le3\cdot8(\lfloor{n/2}\rfloor)^2 + 2n^2\le24(n/2)^2+2n^2=8n^2$$

Note that since $\lfloor{n/2}\rfloor\lt n$, we can apply the induction hypothesis to obtain $T(\lfloor{n/2}\rfloor)) \leq 8(\lfloor{n/2}\rfloor)^2$.

Exercise 1. Show that $T(n) \lt 8n^2$ for all $n >0$.

Exercise 2. What is the largest $n$ such that $T(n) \le 7n^2$?

Exercise 3. Show that $\dfrac{T(n)}{n^2}\to8$ when $n\to\infty$.