a) Let n be a positive integer. Consider the following algorithm segment: X=0; for i=1 to n { for j=1 to i{ for k=i+1 to n { X=X+1; } } } Derive the number of additions (+) performed by this code segment. Note that your answer should be an expression in n. b) Consider the code of this algorithm, insertionSort, which sorts the input array X[1:n] of n elements into an output array Y[1:n) in increasing order, in time T(n) to be determined. int insertionSort( input X[1:n), output: Y[1.n]){ // n is a positive integer If (X has only one element){ Copy X to Y and return; // takes time T(1)=1; } insertSort(X[1.n-1], Y[1.n-1]); // sorts the first n-1 elements of input X, and takes // time equal to T(n-1) insert X[n] into Y[1.n-1); // adds the last element of X in the right location in // the output, in time equal to n } From the comments in the code, we have T(1)=1 and T(n)=T(n-1)+n for all n >1. Compute the value of T(n) as an expression in n