Question

1. (10 pts.) Count the worst-case number of array element comparisons (A[j] < A[j-1]) made by InsertionSort on arrays of size n:

                   void InsertionSort(int A[], int n)
                   {
                           for (int i = 1; i < n; ++i)
                                   for (int j = i; j > 0 && A[j] < A[j-1]; --j)
                                           swap(A[j], A[j-1]);
                   }
                   

   Do the same for the number of swap's.

2. Which function grows faster: 2^((lg?))2 or ?^(2019)? Justify your answer.

3. Use "name and conquer" to give a derivation of the identity:

∑?=0 b^? = (b^(?+1) −1) / (b−1).

Answer 1