Пытаясь понять сложность подсчета сортировки

Question

Читая о разных видах. В случае сортировки с подсчетом, код C ниже работает нормально, но у меня есть вопрос о его сложности времени. На самом деле это не O(N), как я читаю во многих местах, а O (максимальное значение входного массива - минимальное значение массива). который может быть больше чем N. Теперь, если мы увеличим N и одновременно увеличим max - min (диапазон - то есть увеличим max и уменьшим min), тогда сложность во время выполнения может стать квадратичной, то есть O (N²) или нет? Или может быть наихудший случай для такого рода, если входной массив имеет несколько экземпляров с одинаковыми значениями. Не совсем понятно, пытаясь понять.

Предположим, мы вычислили минимальные, максимальные значения для данного массива, которые передаются counting_sort. n - длина входного массива

void counting_sort_mm(int *array, int n, int min, int max)
{
  int i, j, z;

  int range = max - min + 1;
  int *count = malloc(range * sizeof(*array));

  for(i = 0; i < range; i++) count[i] = 0;
  for(i = 0; i < n; i++) count[ array[i] - min ]++;

  for(i = min, z = 0; i <= max; i++) {
    for(j = 0; j < count[i - min]; j++) {
      array[z++] = i;
    }
  } 

  free(count);
}

Answer 1

Без каких-либо дополнительных предположений о конкретных значениях во входном массиве время выполнения сортировки при подсчете равно O(n + U), где U - это значение, которое вы называете max - min. Величины n и U не зависят друг от друга, если у вас нет оснований полагать иначе.

Теперь вполне возможно, что по причинам, характерным для вашего конкретного приложения, случается, что максимальное значение в массиве не более n^2, а минимальное значение 0, в этом случае U = O (n²), В этом случае время подсчета сортировки действительно будет O (n²). Это на самом деле случается приличное количество на практике.