time complexity of relation T(n) = T(n-1) + T(n/2) + n

Question

for the relation

T(n) = T(n-1) + T(n/2) + n

can I first solve the term (T(n-1) + n) which gives O(n^2), then solve the term T(n/2) + O(n^2) ?

according to the master theorem which also gives O(n ^ 2) or it is wrong?

Answer 1

No, you cannot solve it using Mater-theorem.

You need to solve it using Akra–Bazzi method, a cleaner generalization of the well-known master theorem.

1. Master-theorem assumes that the sub-problems have equal size.

2. The master theorem concerns recurrence relations of the form

T(n) = a T(n/b) + f(n) , where a>=1, b>1.

---

I am not deriving here the steps for the solution so that you work out on it. If you have further problem while solving the same, please comment below. Good luck...