Problem 1. For each part, given functions f(n) and g(n), show whether f(n) is Theta(g(n)), omega(g(n ...

---

Problem 1. For each part, given functions f(n) and g(n), show whether f(n) is Theta(g(n)), omega(g(n)), or o(g(n)). The notation lg means logarithm base 2. No explanation is required. (a) f(n) = (n lg lg n)^2, g(n) = n^2 sqrt(n). (b) f(n) = n^2, g(n) = 3^(lg n). (c) f(n) = n^3 + 5n, g(n) = 2^(3 lg n). Problem 2. Consider the following sorting algorithm. It operates in stages from 1 to n - 1. During the ith stage, it finds the minimum element of the subarray A[i..n] and swaps it into its final sorted location A[i]. SomeSort(A[1..n]): for i = 1 to n - 1: min = i; for j = i + 1 to n: if A[j] < A[min] then min = j; swap A[i] with A[min]. This sort is NOT stable. Give an example of an array with exactly 3 integer elements that demonstrates SomeSort is not stable. Label duplicate elements with subscripts (for example 2a, 2b). Problem 3. Suppose we write a version of quicksort such that when an n-element array is being sorted, the pivot is always selected as the element of rank n/5 (you may assume you are using DeterministicSelect to choose the pivot). Let T(n) denote the running time of this algorithm to sort an n-element array. (i) Give the recurrence for this algorithm. (ii) What is the worst-case running time of this algorithm? Solve the recurrence you gave in part (i) by drawing a recursion tree. (You must use Theta notation.)