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?
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