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 = 2m, 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 = 2m,

and gives explicitly the starting and ending value for the index in the series.

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