1. (10 points) (Formally) Prove or disprove T(n) = 0() by using the definitions of the notations involved or disprove it by giving a counterexample. 2. (10 Points) Given the following sorting algorithm, Input: an array of Nintegers, A Output: print out a sequence of integers in an ascending order Algorithm: While (the array is not empty) find the maximum element remove it from the array and display The recurrence for the above algorithm is, T(n) = T(n-1) + n-1. Compute the running time of the recurrence relation using the forward or backward substitution method. 3. (10 Points) Using the master method to compute the sunning time of T(n) = T(2n/3) + 1. 4. (10 Points) Complexity analysis. What is the order of growth of the worst-case running time of the following code fragments? n is the input size. (a) for (int i=0; i<>