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.

  • $\begingroup$ What are your thoughts? How have you tried to analyze its running time complexity? $\endgroup$
    – D.W.
    Commented Oct 8, 2020 at 0:10
  • $\begingroup$ @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 $\endgroup$
    – Dor Eitan
    Commented Oct 8, 2020 at 7:47
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. Do not comment comments: edit your question; you can use $L^AT_EX$ for formulas (in comments, too). $\endgroup$
    – greybeard
    Commented Oct 9, 2020 at 6:06

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.