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.
3
-
$\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 EitanCommented 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$– greybeardCommented Oct 9, 2020 at 6:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
