Radix Sort uses Counting Sort as sub-routine, if there are d digits numbers in the input, then we need d passes of the Radix Sort, and each pass needs O(n+k) time, so total time comes to $O(d*(n+k))$.

As the input elements are in the range of $[1....n^3]$ we can convert each element into base n then each number needs $log_n(n^3) = 3$ digits.

So, there will only need to be **3 passes**, for each pass, there are n possible values which can be taken on.

So, we can use counting sort in $O(n)$ time.