Radix sort's linear run time

220 Views Asked by At

We know that radix sort's run time is $\Theta (d(n +k))$ where n is the no. of elements to be sorted, k is the range of individual digit of the elements ($k =O(n)$) and $d$ is the no. of digits in every element, which is assumed to be constant. I am wondering that if we re-arrange any random list of elements to contain same constant no. of digits we will be able to achieve a $\Theta(n)$ time.

For eg. 5, 72, 99, 343, 2, 8999, 1765, 57, 554, 12

can be rearranged to

0005, 0072, 0099, 0343, 0002, 8999, 1765, 0057, 0554, 0012

now, here $d = 4$ (constant) and also $k= O(n)$ (0 to 9)

We can do this with any random arrangement of numbers and achieve a linear time, Where am I wrong $?$