Я пытаюсь найти, какие значения k дают линейную временную сложность для алгоритма, который сортирует числа в списке в порядке возрастания. Я обнаружил, что O (1) значений k составляет алгоритм O (n), но я слышал, что существуют другие значения k, которые я не могу найти. Псевдокод вставлен ниже. Любая помощь будет оценена!
""" PSEUDOCODE
Function sort(a)
A <- new dict
K <- new array
M <- new array
For i in a
A.add {i:0}
For i in a
A[i] <- A[i]+1
For key in A.keys
K <- add key
K <- Quicksort (K)<br>
For k in K
M = M + [k]*A.value(k)
return M
"""