O Radix Sort é um algoritmo que ordena números inteiros considerando seus dígitos, e sua eficiência depende da estabilidade do método de ordenação usado para cada dígito. Suponha que você tenha um conjunto de números de d dígitos e utilize o Counting Sort como método estável para ordenar cada dígito.

Considerando que o Counting Sort tem complexidade O(n + k), onde k é o intervalo dos dígitos, qual é a complexidade total do Radix Sort e sob quais condições ela se mantém linear em n?