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.

Please see here

This solution says T(n) = O(2^n) and T(n) = omega(n^2) and does not explain how.

Also see here

This solution says T(n) = O(n^2). but contradicts with above solution