[20 pts] Recall that Insertion Sort on an array A:= [a1,.,a,] of distinct real numbers consists of scanning each position i = 2,...,n in the array, and at each i, inserting a, into its proper relative position among a1,..,a;-1 by comparing it sequentially to the values at indices i-1, i-2,... 2,1 as necessary. Let C(n) denote the number of element comparisons made by Insertion Sort. (a) [10 pts] Determine an exact formula for the worst-case number of comparisons required, and indicate the array(s) on which this worst-case is achieved. (b) [10 pts] If the original ordering is a uniformly random permutation on a set S of n distinct elements, and Ca(n) is the average (expected) number of comparisons required, determine the dominant term (including its constant) of Ca(n)