4. (35 points) Algorithm A is a divide-and-conquer type with a time complexity given by the

following recurrence relation: 7(n)= T (2n/3) + T (n/3) + n. Answer the following questions

about the recursive tree of A on input size n-3", where 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 /?

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

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 =3",

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

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