Radix Sort uses Counting Sort as sub-routine, if there are d digits numbers in the input, then we need d passes of the Radix Sort, and each pass needs O(n+k) time, so total time comes to $O(d*(n+k))$.

As the input elements are in the range of $[1....n^3]$ we can convert each element into base n then each number needs $log_n(n^3) = 3$ digits.

So, there will only need to be **3 passes**, for each pass, there are n possible values which can be taken on.

So, we can use counting sort in $O(n)$ time.

Following algorithm(s) can be used to sort $n$ in the range $[1\ldots n^3]$ in $O(n)$ time

- Heap sort
- Quick sort
- Merge sort
- Radix sort

### 8 Comments

## 5 Answers

Answer is $(D)$ Part.

Although people have provided correct answers but it seems some more explanation is required.

Let there be $\mathbf{d}$** digits** in max input integer, **b is the base** for representing input numbers and $\mathbf{n}$** is total numbers** then **Radix Sort takes **$\mathbf{O(d*(n+b))}$** time**. Sorting is performed from least significant digit to most significant digit.

For example, for decimal system, $b$ is $10$. What is the value of $d$? If $k$ is the maximum possible value, then $d$ would be $O(\log_b (k))$. So overall time complexity is $O((n+b) * \log_b(k))$. Which looks more than the time complexity of comparison based sorting algorithms for a large $k$. Let us first limit $k$. Let $k \leqslant n^{c}$ where $c$ is a constant. In that case, the complexity becomes $O(n \log_b(n))$. But it still does not beat comparison based sorting algorithms.

What if we make value of $b$ larger?. What should be the value of $b$ to make the time complexity linear? If we **set **$\mathbf{b}$** as **$\mathbf{n}$** then ** we will get the time complexity as $O(n)$.

In other words, we can sort an array of integers with range from $1$ to $n^{c}$, If the numbers are represented in base $n$ (or every digit takes $\log_2(n)$ bits).

Reference: http://www.geeksforgeeks.org/radix-sort/

### 8 Comments

While we are setting b as n(or more specifically it should be n^c as k<=n^c) resulting in O(n).

But as we initially neglected "b" being a constant value of 10, How can we neglect "b" now (b=n^c which is not constant)?

**O(d∗(n+b)) will now be O(logb(k) ∗(n+n^c)) making it asymptotically O(n^c) and **

**here we have c=3[ as k=n^3], So, shouldn't that result in O(n^3)?**

Please explain?Thanks.

I have one doubt..is this thing efficient for all cases?

Like for cases where we need to reduce the b value. For eg: initially say b=10 and n=5 and the numbers in the array are {1,56,3,176,849}.

k=849 and ceil(log_{10}k)=3. 849 <= n^{5} where c=5 (849<=3125).

O(nclog_{10}n) = O(4*n*3)

Now if we make b=n then b becomes 5 which is less than initial value.

So all numbers are now to be represented in base 5.

(1)_{10}=(1)_{5 }, (56)_{10}=(211)_{5 }, (176)_{10}=(711)_{5} , (849)_{10}=(11344)_{5}, (3)_{10}=(3)_{5}

Now the array is { 1,211,711,11344,3} which means no. of times counting sort to be applied increases [since radix sort is basically applying counting sort on every bit starting from lsb to msb].

So doesn't this increase the time taken?

I got another example where b=2 and in that case if we have to increase b to 10 then the no. of digits get reduced and hence the time.

Concluding my confusion : Does this technique work only when b has to be increased..?

Initially you can figure it out that Merge Sort has O(nlogn) and Quick Sort has O(n^2) and Insertion Sort has O(n^2) as worst case time complexity and Merge Sort has O(nlogn) and Quick Sort has O(nlogn) and Insertion Sort has O(n) as best case time complexity. Insertion Sort gives best case if array is sorted or almost-sorted. But here nothing is given about elements of array.

So ans would be Radix Sort only. Also, the idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, example Decimal.

### 8 Comments

@srestha mam, Radix Sort sorts digit by digit from least significant to most significant. Digits can take value from 0-9 range so for every digit we perform Counting Sort so subroutine as Counting Sort required, please correct me if I am wrong

@srestha mam, We always chooses from worst cases, because question tell us nothing about how elements are placed in array, we have to consider worst cases only, Insertion Sort and Bubble Sort both give O(n^2) in worst case but Radix Sort give O(n) in worst case that is why i am considering Radix Sort. (Range is given for elements which is [1-n^3])

@srestha mam, I think i might be missing that point here, I thought that most probable answer could be Radix Sort only as Radix Sort is not comparison based sort (it is counting sort), if not Radix Sort then it should definitely be Insertion Sort