Prove by induction $T(n) = T(\lfloor\frac{n}{2}\rfloor)+n^2 \in \Theta (\log_2 n)$

Text of the problem:

Solve the following recurrence equation and prove it by applying the principle of induction: $$T(n) = \begin{cases} 3, \ n \le 2 \\ T(\lfloor\frac{n}{2}\rfloor)+n^2, \ n \ge 3 \end{cases}$$

after doing the recursion tree, I find that the complexity (if I'm not wrong) is $$\Theta (\log_2 n)$$

But I don't know how to do the induction step.

• @PålGD $T(n) \in O(n^2) ?$ Nov 3 at 22:59
• I thought so because when I went to each recursive call I work only on half of the previous one, so the height of the call tree should be $\log_2 (n)$ and the complexity $\sum_ {i = 1} ^ {\log_2 (n)} costwhile = \sum_ {i = 1} ^ {\log_2 (n)} \theta (1) = \theta (\log_2 (n))$. do I have to think differently? Nov 4 at 13:50
• What do you mean with the notation $[ x ]$? Nov 4 at 14:15
• @Steven with $[x]$ I mean the floor, but I'm not able to write it in LaTeX. Nov 4 at 14:26

First of all note that $$T(n)$$ is indeed not in $$\Theta(\log n)$$, which makes the proof difficult.

You need to understand that if $$T(n) = T(n/2) + n^2$$, then $$T(n) = \Omega(n^2)$$, since it uses $$n^2$$ time in the first "iteration" or "level".

You have made a mistake when drawing the call tree. The call tree will look like this:

$$n^2 + \left(\frac{n}{2}\right)^2 + \left(\frac{n}{4}\right)^2 + \left(\frac{n}{8}\right)^2 + \cdots + \left(\frac{n}{2^i}\right)^2$$

You are right that the "tree" (or path) terminates after $$\log_2(n)$$ calls, so the summation should look like

$$\sum_{i=1}^{\log_2 n} \left( \frac{n}{2^i}\right)^2 = \sum_{i=1}^{\log_2 n} \left( \frac{n^2}{2^{2i}}\right) = n^2 \cdot \sum_{i=1}^{\log_2 n} \left( \frac{1}{2^{2i}}\right) = n^2 \cdot c,$$ for some constant $$c$$.

Now, since $$T(1) = 3$$, let's try to prove by induction that $$T(n) \leq 3n^2$$.

• Base case 1: $$T(1) = 3 \leq 3\cdot 1^2 = 3$$
• Base case 2: $$T(2) = 3 \leq 3\cdot 2^2 = 12$$
• Induction hypothesis: $$T(n') \leq 3n^2$$ for all $$n' < n$$.
• Induction step: $$T(n) = T(n/2) + n^2 \leq 3 \left(\frac{n}{2}\right)^2 + n^2 = 3/4 n^2 + n^2 \leq 3n^2$$.
• Ps, if it weren't for the fact that $T(1) = 3$, you could show that $T(n) \leq 1.33333n^2$, where $c = 1.33333 \sim \sum_i^\infty 1/2^{2i}$. Nov 4 at 14:34