Define the problem of sorting of an array x[1..n] using quick sort as a recursive problem. Formulate and solve the recurrence equation and then, using the definition of the worst case time complexity, prove that T(n) is O(nlog2 n). Define the problem of finding the maximum of an unsorted array x[1...n] as a recursive problem. Formulate a recurrence equation for T(n) for this problem. Solve this recurrence equation and, then, using the definition of the worst case time complexity, prove that T(n) is O(n). n^3 > 7n^2 + a Forall n greaterthanorequalto n_0. Here a is a constant. What is n_0? Compute n_0 algebraically as well as by formulating a table. Assume a = 5 for the purpose of formulating table. Using the definition of complexity- prove that O(n^3 + 4n^2) is the same as O(n^3). Also, prove that O(n^3 - 4n^2) is the same as O(n^3). Given the array [4, 3, 2, 5, 7], precisely how many comparisons and swaps will be required to sort the array in ascending order using the O(n^2) sorting algorithm given in the class. Using the definitions for big "O" notation, can you prove that T(n) = 4n^2 - n^3 + 100 is O(n^3) for some positive constants c and n_0? Explain your answer. Consider the problem of printing an array A[1...n]. Let T(n) be the time required to solve this problem. Do the following for this problem: (a) Define the problem recursively, (b) formulate a recurrence equation for this problem, and (c) solve this recurrence equation. Solve the following recurrence equation: T(n) = a, if n = 1 T(n) = b + T(n/2), else. Prove by induction that T(n) = a + b log2 n. Assume that n -= 2^m. What is the MST property? Prove, by contradiction, that all minimum cost spanning trees satisfy this property. Do the depth first search for the following graph and name the arcs as tree, back, cross, and forward arcs