2. Consider this recurrence: S4T(n/3) + 2n when n > 1, T(n) = 1 when n= = 1. (a) How many levels will the recurrence tree have? (b) What is the cost at the level below the root? (c) What is the cost at the lth level below the root? (d) Is the cost constant for each level? (e) Find the total cost for all levels. Hint: You may need to use a summation. The Geometric Sum formula may be helpful. (f) If T(n) is O(g(n)), find g(n). Solution