This is a question in a data structures course asking about the complexity of the following course. I know that the final answer is O(n^2), but I need an explanation of how can we get there using summations. Appreciate the help

Consider the following Shell Sort java implementation:

public int shellSort(int arr[], int n) {

// Start with a big gap, then reduce the gap

for (int gap = n/2; gap > 0; gap /= 2){

// Do a gapped insertion sort for this gap size.

// The first gap elements a[0..gap-1] are already in gapped order

// keep adding one more element until the entire array is gap sorted

for (int i = gap; i < n; i += 1) {

// add a[i] to the elements that have been gap sorted

// save a[i] in temp and make a hole at position i

int temp = arr[i];

// shift earlier gap-sorted elements up until the correct

// location for a[i] is found

int j;

for (j = i; j >= gap && arr[j - gap] > temp; j -= gap){

arr[j] = arr[j - gap]; // MyStatement4

// put temp (the original a[i]) in its correct location

arr[j] = temp;

}

}

return 0;

}

By focusing on the number of times MyStatement4 gets executed, find the time complexity of the above algorithm in terms of Big O notation in the worst case? Is it different from the best case? Justify your answer.

(find how many times MyStatement4 gets executed, the answer should look like : T(n) = n^2+n+1 = O(n^2))