In the pseudocode the array to be sorted is \(A\)  and the number of digits in the largest integer is \(d\) . If we use the counting sort each pass will use \(\Theta (n+k)\)  time, where each digit is in the range of \(0\ldots k-1\) . The whole sort takes \(d\)  passes, so the total time usage is \(\Theta (d(n+k))\) . [1]}.
