the results.) Solve the following recurrences using the Master Theorem. (You can directly give 1. T(n) = 8T(n/2) + 3n - 9n 2. T(n) 8T(n/2) + 2n - 100m 3. T(n) = 4T(n/2)+n + 5 logn 4. T(n) = 8T(n/2) + n +nlogn 8T(n/2) + 4n 5. T(n) 6. T(n) = 4T(n/2)+2-10n4-6n3 Problem 2 (20 points). Propose TWO example recurrences that CANNOT be solved by the Master Theorem. Note that your examples must follow the shape that T(n) = aT(n/b) + f(n), where n are natural numbers, a > 1, b > 1, and f(n) is an increasing and non-negative function. Explain why your recurrences cannot be solved by the master theorem. Problem 3 (30 points). Given the root of an existing binary search tree (BST) which is quite balanced and contains n distinct keys, you are asked to design a O(n log n)-time algorithm that will create a copy of the given BST. By "copy" we mean (1) the two trees have the exactly same topological structure; (2) between the two trees, for each pair of two nodes that occupy the same topological position, they contain the same key. Activate Wind