java - Shell排序算法时间复杂度

Question

我被告知要在课堂上展示 Shell Sort，我做到了。我进行了很多研究，只是为了看到他们中的大多数都写了 O(n log n) 以获得最佳情况时间复杂度。然而，在向我的老师展示了这个算法之后：

import java.util.Arrays;

class ShellSort{
  void shellSort(int array[], int n){
    for (int gap = n/2; gap > 0; gap /= 2){
      for (int i = gap; i < n; i += 1) {
        int temp = array[i];
        int j;
        for (j = i; j >= gap && array[j - gap] > temp; j -= gap){
          array[j] = array[j - gap];
        }
        array[j] = temp;
      }
   }
}

  public static void main(String args[]){
    int[] data={9, 8, 3, 7, 5, 6, 4, 1};
    int size=data.length;
    ShellSort ss = new ShellSort();
    ss.shellSort(data, size);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

我的老师马上反驳我说“这个排序算法最多只有n^3”。

她忘了教我们如何获得程序的时间复杂度，所以我在这里迷路了。