2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.