Exercise I (25 points) (See Appendix...) Consider two algorithms A1 and A2 that have the running times T1(n) and T2(n), respectively. T1(n)=100n2+100nlg(n)andT2(n)=0.1n2+0.1nlg(n) a) (24 points) Use the definition of O( used in this course (textbook) to show that T1(n)O(T2(n)). Hint: See Slide 28 or Textbook Pages 44-49. You will have to find/exhibit the numbers c and n0. b) (I points) Which algorithm should you use? A1 or A2 ? Exercise 2 (20 points) (See Appendix...) Consider two algorithms Ai and A2 that have the running times T1(n) and T2(n), respectively. T1(n)=100n2+100nlg(n) and T2(n)=0.1n2+0.1nlg(n) a) (15 points) Use the definition of used in this course (textbook) to show that T1(n)(T2(n)). Hint See Slide 28 or Textbook Pages 44-49. You will have to find/exhibit the numbers c and n0. b) (5 points) Show that T1(n)(T2(n)) using the most compelling and concise arguments. Hint use what you already established in this exercise and the previous exercise. Exercise 3 (20 points) List all the functions below from the lowest to the highest order (in terms of growth). Functions with similar growth () must be grouped between brackets (D). Brief justifications are ok. n6nnlg(n)ln(n)lg(n)nn4 Consider the algorithm getindexMinimumilals that takes a sequence A as an input and returns the inde: of the smallest number (minimum) in the range [kA alength ] in Sequence A. For example, let A={100,2,14,5,22,7}. getlndexMinimum(A.3) will return 4 becouse 4 is the index of the element 5 and 5 is the smollest number in A in the range [3-6]. We assume that getindexMinimum (A,k)costs2(nk)+1 comparisons where n= A.length. Consider the following sorting algorithm that sorts a sequence A in increasing order. Sort-Array (A) 0: n=A length 1: for j=1 to n 2: IndexMin = getindexMinimum (A,i]) II Swap A[j] and A.IndexMin] 3: buffer =A[ IndexMin] 4: A[IndexMin] =A[j] 5: A[J]= buffer The objective is to find the total number comparisons performed by the above algorithm Sort-Array= a. (1 point) How many comparisons in total are performed by the "for loop" statement in Line 1 during the execution of the algorithm? b. (20 points) Let us call Q the number of comparisons performed by getindor Minimum (a) (Line 2). Fill in this table (Justify how you determine oi): C (10 points) Based on b, express the total number of comparisons performed by cetladexMinimum (A1) in Line 2 during the execution of the aigorithm. d. (1 point) Express the function f0(n) that represents the overall total number of comparisons performed by the statements in Lines 2 and 4 during the execution of the algorithm. e. (3 points) What is the time complexity of Sort-Array