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

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

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

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