Изменения

Пусть <tex>k</tex> {{- --}} количество разрядов, <tex> n </tex> {{- --}} количество входных данныхобъектов, которые нужно отсортировать, <tex>T(n)</tex> {{- сложность --}} время работы устойчивой сортировки. Цифровая сортировка выполняет <tex> k </tex> итераций, тогда сложность на каждой из которой выполняется устойчивая сортировка и не более <tex> O(1) </tex> других операций. Следовательно время работы цифровой сортировки {{- --}} <tex>ОO(k*\cdot T(n))</tex>.При использовании сортировки подсчетом получаем линейную зависимость.