0
$\begingroup$

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

$\endgroup$
2
  • 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 at 13:45
  • $\begingroup$ @Steven I am sorry. I wanted to write Substitution method. $\endgroup$ – Diana Feb 21 at 13:53
0
$\begingroup$

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
$\endgroup$

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.