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 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 at 13:50
  • $\begingroup$ What do you mean with the notation $[ x ]$? $\endgroup$
    – Steven
    Nov 4 at 14:15
  • $\begingroup$ @Steven with $[x]$ I mean the floor, but I'm not able to write it in LaTeX. $\endgroup$ Nov 4 at 14:26
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 at 14:34

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.