Recursion Tree please provide neat solution for full points

Recursion Tree please provide neat solution for full points and good feedback thanks

For each of the following recurrences, give a one-line answer to the following questions: When you construct a recursion tree of the recurrence relation, how many leaves does it have? what is the height of the tree? how many nodes does it have? T(n) = 4T(n/2)+n^2 T(n) = T(n - 1) + n T(n) = 3T (n/5) + n^3 T(n) = T(n/3) + T(2n/3) + squareroot n You may assume that T(n) = 1 for n lessthanorequalto 1

Solution

1. T(n). = 4T(n/2) + n2
a . The number of leaves is n^log_ba     =>n^log₂4 => n² .
b . Height is log₂ n.
c . Total number of nodes is 1 +4 +4²+ 4³+........+4^h = > 4^{log ₂n} => Roughly n³


2. T(n) =T(n-1) + n
This will reduce down by 1 and we will get only 1 leaf
a . The number of leaves is 1.
b . Height is n.
c . Total number of nodes is 1 +1 + 1 +1 + upto h = > n

3. T(n). = 3T(n/5) + n³
a . The number of leaves is n^log_ba     =>n^log₅3 => n .
b . Height is log₅ n.
c . Total number of nodes is 1 +3 +3²+ 3³+........+3^h = > 3^{log ₅n} => Roughly n²

4. T(n). = T(n/3) + T(2n/3) + sqrt(n )
a . The number of leaves is max   <= n .
b . n/3 grows faster than 2n/3 so Height is log_3/2 n.
c . Total number of nodes will lie between log₃ n N log_3/2 n. we can say roughly n