La complexité du counting sort dépend de deux paramètres principaux : le nombre d'éléments 
𝑛
n à trier et la plage 
𝑘
k des valeurs possibles dans le tableau.

Complexité temporelle
Temps d'exécution : 
𝑂
(
𝑛
+
𝑘
)
O(n+k)
Explication :

Initialisation du tableau de comptage : 
𝑂
(
𝑘
)
O(k) (parcours de la plage 
𝑘
k).
Comptage des occurrences : 
𝑂
(
𝑛
)
O(n) (parcours des 
𝑛
n éléments).
Reconstruction du tableau trié : 
𝑂
(
𝑛
+
𝑘
)
O(n+k) (parcours du tableau de comptage et reconstruction).

Cas optimal, moyen et pire : 
𝑂
(
𝑛
+
𝑘
)
O(n+k) dans tous les cas, car le counting sort n'est pas un algorithme comparatif. Sa performance dépend uniquement de 
𝑛
n et 
𝑘
k.

Complexité spatiale
Espace supplémentaire : 
𝑂
(
𝑛
+
𝑘
)
O(n+k)
Explication :
Un tableau de taille 
𝑘
k pour stocker les comptes.
Un tableau de taille 
𝑛
n pour stocker le résultat trié.

Remarques
Efficacité : Le counting sort est très efficace lorsque 
𝑘
k est de l'ordre de 
𝑛
n ou inférieur (par exemple, 
𝑘
=
𝑂
(
𝑛
)
k=O(n)). Si 
𝑘
k est très grand (par exemple, 
𝑘
≫
𝑛
k≫n), l'algorithme devient moins efficace en temps et en espace.
Stabilité : Le counting sort est un algorithme de tri stable (l'ordre relatif des éléments égaux est préservé).

Exemple
Si 
𝑛
=
100
n=100 et 
𝑘
=
50
k=50, le nombre d'opérations est de l'ordre de 
150
150, ce qui est très efficace. En revanche, si 
𝑘
=
1
000
000
k=1000000, il passe à environ 
1
000
100
1000100, ce qui est nettement moins optimal.