2. Use the recursion tree method to solve the following recurrence:

2. Use the recursion tree method to solve the following recurrence: ns6 T(n) 3T(n/6) +n n 6 a) 5 marks] Draw the levels 0, 1, and 2 of the recursion tree. Then, determine the height of the recursion tree. [10 marks] Find a pattern for the amount of work at level i, and then convert the total amount of work in the tree to a summation. Find an upper bound for that summation, and obtain the answer b) Hint: In this recursion tree the amount of work will not be the same in all levels, so, you cannot just multiply the number of levels by the amount of work on each level. Instead, solve the