1
$\begingroup$

Okay so I have this recursive formula

$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2*O\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\left(n\right)⌋}\frac{1}{2^{k}}=T\left(1\right)+c_{2}*(n-1)$

I've been trying for a few hours to prove the correctness of it by induction, I feel like I've tried everything. The closest I got was defining $n=2^{x}$ and prove 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$
0
$\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$ – MathCurious Apr 27 at 12:37
  • $\begingroup$ I edited my question to be more specific. :) $\endgroup$ – MathCurious Apr 27 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 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 at 12:44
  • $\begingroup$ My problem is that I'm not able to prove the recursive formula by induction $\endgroup$ – MathCurious Apr 27 at 12:54

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.