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).
Fig: 1