Algorithm A is a divide and conquer type with recurrence relation Argue that the solution to the recurrence T (n) = T (n/3) + T (2n/3) + n. Answer the following questions about the recursive tree of A on input size n = 3^m, where m is a positive integer.

a.The tree root starts at level 0, then what is the input size to a node at level i?

b.How many nodes at level i?

c.How much total work is actually done at level i?

d.The root is at level 0. What level are the leaves at?

e.Write a series that represents the running time for the algorithm for inputs of size n = 3^m, and gives explicitly the starting and ending value for the index in the series.

f.Give the tightestbig-O bound for T(n)