Use a recursion tree for the following algorithms to find th

Use a recursion tree for the following algorithms to find the running time. T(n) = T(n - 1) + n T(n) = 2T(n/3) + n^2

Solution

2)2T(n/3)+n^2

Subproblem size at level i = n/3ⁱ

At level i:Cost of each node=c(n/3ⁱ)²   

# of nodes=2ⁱ Total cost= n²(2/9)ⁱ

h=height of the tree ->log₃n

Therefore,T(n)=O(n²)