VIII. (10 points) Applying the Master Theorem to the recurrence equation TU) = 7T(n/4) + 4n + 2; T(1)-0 Yields the result that T(n) is in Applying the Master Theorem to the recurrence equation T(n) = 2T(n/2) + n; T(1) = 1 Yields the result that T(n) is in (a) (mg47) (b) e(log n) (c) e(nlogn) (a) e(n) (b) (log n) (c) (nlogn) (e) None of the above (e) None of the above IX. (10 points) In Merge Sort when the array is given in reverse sorted order, eg, 8 7 65432 1, the complexity function (counting a comparison as the basic operation) is (a) nlgn-n+1 nlgn+n- 1 (nlgn)/2 d) n2 (e) Neither equal to the worst case nor the best case X. (10 points) The every-case complexity function T(n) for an algorithm input on an input of that size size of the input input of that size (a) maps the input into the number of basic operations executed with that (b) maps the size of the input into the number of basic operations executed maps the number of basic operations executed by the algorithm into the (d) maps the size of the input into the running time for the algorithm with arn (e) maps the input into the running time for the algorithms with that input