1
$\begingroup$

I have this recursive formula

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)$$

$$T\left(n\right) =T\left(1\right)\ +\ c_{2}n\cdot\sum_{k=1}^{⌊\log n⌋}\frac{1}{2^{k}}=T\left(1\right)+c_{2}(n-1)$$

I've been trying for a few hours to prove its correctness by induction, I feel like I've tried everything. The closest I got was defining $n=2^{x}$ and proving the correctness for every $x$, but I can't seem to get the right answer. How do you prove something like that?

The main question is how do I prove $T(n) = T(n/2) + c_{2}n = T(1) + c_{2}(n-1)$.

$\endgroup$

1 Answer 1

1
$\begingroup$

The series $\frac{1}{2^k}$ is a geometric progression. Hence, $\sum_{k=0}^m \frac{1}{2^k} = \frac{1-\left(\frac{1}{2}\right)^m}{1-\left(\frac{1}{2}\right)}$

You can continue from here.

$\endgroup$
5
  • $\begingroup$ Hey, thanks for the reply. I'm aware of what you wrote but I don't know how to do that induction.. $\endgroup$ Apr 27, 2021 at 12:37
  • $\begingroup$ I edited my question to be more specific. :) $\endgroup$ Apr 27, 2021 at 12:39
  • $\begingroup$ If you managed to show that $T(n)=T(1)+c\cdot n\cdot \sum_{k=1}^{\lfloor \log(n) \rfloor} \frac{1}{2^k}$, then substitute the formula in this answer. If you didn't manage to prove this, then try to prove it using induction. Do not skip over the step of showing $T$ as a summation! it will only make it harder for you to prove it by induction $\endgroup$
    – nir shahar
    Apr 27, 2021 at 12:43
  • $\begingroup$ If you would rather not go through this step (of showing that $T$ can be expressed as a summation), you can find some constant $c>0$ that suits you, and prove by induction that $T(n) \le T(1) + c\cdot n$ $\endgroup$
    – nir shahar
    Apr 27, 2021 at 12:44
  • $\begingroup$ My problem is that I'm not able to prove the recursive formula by induction $\endgroup$ Apr 27, 2021 at 12:54

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.