# Calculating the Time complexity using Radix sort

Im trying to determine what is the time complexity of sorting numbers with a specific range and base. I have n numbers in the range of 1-n^10 and the base for the radix sort is n/log n. I have tried to calculate it using log equations but im getting to a linear result, I dont know wether im right or wrong. Thank you very much.

• What are your thoughts? How have you tried to analyze its running time complexity?
– D.W.
Commented Oct 8, 2020 at 0:10
• @D.W. i tried to convert n^10 to n/log n base using the formula: (n/log n)^d = n^10 and then using log on both sides: d*log(n/log n) = 10 log(n) => d = 10 log n/ (log (n/logn)) and then the time complexity of the radix sort is: d(n+k) => using the d that i found i think its linear Commented Oct 8, 2020 at 7:47
• Welcome to COMPUTER SCIENCE @SE. Do not comment comments: edit your question; you can use $L^AT_EX$ for formulas (in comments, too). Commented Oct 9, 2020 at 6:06

You are correct. We have $$(n/\log n)^{20} \le n^{10}$$ for all $$n\ge 1$$, so each number can be expressed using at most $$d=20$$ "digits". The running time of radix sort is $$O(dn)$$, and $$O(20n)$$ is $$O(n)$$, so the running time is linear in $$n$$.