2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @PålGD $T(n) \in O(n^2) ? $ $\endgroup$ Nov 3, 2021 at 22:59
  • $\begingroup$ 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? $\endgroup$ Nov 4, 2021 at 13:50
  • $\begingroup$ What do you mean with the notation $[ x ]$? $\endgroup$
    – Steven
    Nov 4, 2021 at 14:15
  • $\begingroup$ @Steven with $[x]$ I mean the floor, but I'm not able to write it in LaTeX. $\endgroup$ Nov 4, 2021 at 14:26

1 Answer 1

2
$\begingroup$

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$.
$\endgroup$
1
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Pål GD
    Nov 4, 2021 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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