enter image description here

I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to continue? enter image description here

  • 1
    $\begingroup$ You say that you want to solve the recurrence using the Master theorem, but then your proof is by induction. Which of the two is it? Besides your proof is incomplete (no base case, no choice of $c$). $\endgroup$
    – Steven
    Feb 21, 2021 at 13:45
  • $\begingroup$ @Steven I am sorry. I wanted to write Substitution method. $\endgroup$
    – Diana
    Feb 21, 2021 at 13:53
  • $\begingroup$ If $n$ is even, then $\frac n2-\frac12$ is not integer ! By the way, having a solution fir even $n$ is far from being sufficient, because $\frac n2$ might very well be odd. $\endgroup$
    – user16034
    Mar 18, 2022 at 19:41

2 Answers 2


If you have a solution for all even numbers, it might be sufficient to realize $T(k+1) \ge T(k)$.

But generally this is proved by induction where the even numbers use the odd ones. There, you have two leads :

  • Take good care of your bounds during your induction
  • More simple (but with less efficient approximation) : prove it for powers of two with a given constant ; and then use those to prove the general case for another constant

If $n$ is even then

$$T(n)=2T\left(\left\lfloor\frac n2\right\rfloor\right)+n$$ and

$$T(n+1)=2T\left(\left\lfloor\frac{n+1}2\right\rfloor\right)+n+1=2T\left(\left\lfloor\frac n2\right\rfloor\right)+n+1=T(n)+1>T(n).$$


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.