Radix Sort Problem

Question

The complexity of Radix Sort is $O(wn)$, for $n$ keys which are integers of word size $w$.

Here, $w=log_2(n^k)=k\times log_2(n)$

So, the complexity is $O(wn)=O(k\times log_2(n)\times n)$

For instance if size is $n^3$ the complexity would be $O(3nlogn) = O(nlogn)$

Then why we say radix sort sorts the input in linear time?

Similar Concept used to solve : https://gateoverflow.in/3353/gate2008-it-43

Answer 1

Radix sort sorts the input in linear time only in special cases not in all cases. Like input size is nearly equal to word size.
Example:- Suppose base system is 10.

Answer 2

But if you change the base '10' into base 'n' ,then each digit for every no. in the range will be 3.

So if d=constant , time complexity = 0(constant.(n+n)) : 1st 'n' is the no. of elements , 2nd 'n' is the range of each digit.

So time complexity= 0(n).

Answer 3

W = log(base 10 n^k) ... (This will give number of iterations)

 

Radix sort uses counting sort , suppose counting sort uses 10 buckets.

Therefore total time taken for each iteration = initialisation of 10 buckets + putting n elements in bucket = O(n)

Therefore total time ,

Tc = total iteration X time taken for each iteration = klog(n) X n = nklog(n) ...( Base of log is 10)