the results.) Solve the following recurrences using the Master Theorem. (You can directly give 1. T(n)...

 

Transcribed Image Text:

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 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