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 :
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