# How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?

I am aware that to get a running time by recursion tree method, we need to draw a tree and find:

a) number of levels in tree.

Since left side of tree decreases by 1 in size, so it’s longest path from root. Subproblem size at level i is `n-i` . setting n – i = 1 when it hits a size of 1, we get number of levels, i = n – 1.

b) cost per node in tree : `cn`

c) Number of nodes at level i: This is where i am stuck. Not able to find nodes at level i since left side decreases by 1, right side by half. Naturally, tree is more dense towards left side. Not every node will have two children.

if i can get answer to c, i can calculate T(n) = cost of level 0 + cost of level 1 + cost of level 2 + … cost of level n-1. if y1 is number of nodes at level 1, y2 at level 2, etc… then
=> T(n) = cn + y1 * cn + y2 * cn + y3 * cn + …. yn-1 * cn to get total cost.

Can anyone guide me to the approach i am taking ? is it correct ? can i take an assumption that for sufficiently large n, we can ignore T(n/2) and then proceed ? .

Online searching confused me. Problem is 4.4-5 from CLRS.