Question

What is O(g(n)) for the following method? What sorting algorithm is this? /*Function to sort array using ??? sort*/ void sort(int arr[]) { int n = arr.length; for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } }

Answer 1

/*Function to sort array using ??? sort*/
void sort(int arr[]) {
   int n = arr.length;
   for (int i = 1; i < n; ++i) {
       int key = arr[i];
       int j = i - 1;
       /* Move elements of arr[0..i-1],
       that are greater than key,
       to one position ahead of their current position */
      
       while (j >= 0 && arr[j] > key) {
           arr[j + 1] = arr[j];
           j = j - 1;
       }
       arr[j + 1] = key;
   }
}

This is insertion sorting algorithm.

Analysis of time complexity:

Insertion sort
1. Scans through all elements in array
2. Compare and perform swaps , if elements are out of order.

Best case :
If the input array is already in sorted order, insertion sort compares O(n) elements and performs no swap. Therefore, in the best case of insertion sort O(g(n)) = O(n) time.

Worst and Average Case:
If the input array is not in sorted order.
To insert the nth element, at most n-1 comparisons and at most n−1 swaps are required .
To insert the second last element, at most n-3 comparisons and at most n-3 swaps are required.
To insert the third last element, at most n-3 comparisons and at most n-3 swaps are required.
and so on.

Applying formula to get sum of n -1 elements:

2(n−1)(n−1+1)/2 ~ n(n−1).

n(n−1) <= C.n² = O(n²) where C > 0.

Therefore, in the worst case of insertion sort O(g(n)) = O(n²) time.