1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What are your thoughts? How have you tried to analyze its running time complexity? $\endgroup$ – D.W. Oct 8 '20 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 Oct 8 '20 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 Oct 9 '20 at 6:06
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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