1
$\begingroup$

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?

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