Сложность времени сортировки сортировки

Я беру курс алгоритмов, и там я увидел, что временная сложность подсчета сортировки - это O (n + k), где k - диапазон чисел, а n - размер ввода. Мой вопрос: когда разница между k и n слишком велика, например, когда k = O (n ²) или O (n ³), можно сказать, что сложность O (n ²) или O (n ³)? Тогда в этом случае подсчет сортировки не является разумным подходом, и мы можем использовать сортировку слияния. Я прав?

Ответ 1

Да, вы абсолютно правы по всем пунктам.

Кроме того, мы можем сделать более сильные утверждения: когда k = O (n ²) или O (n ³), можно сказать, что сложность сортировки Θ (n ²) или Θ (n ³).

Ответ 2

Вы можете сортировать в O (n) время, теоретически. Если диапазон значений составляет от 1 до n ³ то преобразуется в base n и выполняет сортировку Radix. В базе n число имеет 3 цифры, поэтому ваше время выполнения - O (3n + 3n) + O (n) для базового преобразования. Общий O (n).