Several algorithms have a loop structure that iterates n times and for the k-th iteration, they perform on the order of k2 operations. In this case, the running time of the loop can be obtained by k2. In this problem, we will derive a closed formula for this sum and show that the sum is O(ui) 1. A telescoping sum is a sum of the form -i (aj - a-1). It is easy to see that this sum equals an -do (try it for example for j 4). In class, we stated that k-n(n + 1 )(2n + 1 )/6. Derive this formula using the telescoping sum. Hint: Take ak-: k 3 in the telescoping sum. 2. Show that () by explicitly finding the values of the constants k and C and demonstrating the result