# How to solve the recurrence relation [closed]

How to solve the recurrence relation:

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


by recursion tree to get an asymptotic upper bound?

The height is n, but how to generalize the sum at each levels?

• Hm, this looks like homework... – Ryan Williams Sep 4 '10 at 9:24
• IMHO also off-topic. – Kaveh Sep 4 '10 at 12:37
• Reported in the "to-close" thread on meta. Fauzil, if you want a reference, go check Brassard&Bratley, or Cormen Leiserson Rivest & Stein. – Michaël Cadilhac Sep 4 '10 at 13:39
• Closing as homework. If this was incorrect, please explain on meta in the linked thread. – Suresh Venkat Sep 4 '10 at 15:13
• The tag is inappropriate but the subject matter...where wlse would one ask his kind of question (it's not solvable in 'closed form'). – Mitch Sep 5 '10 at 1:35