1.9k views

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

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

1. Heap sort
2. Quick sort
3. Merge sort
edited | 1.9k views
+13

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.

+2

0
Puja thanks
0
beyond awesome! explanation
0
0

I have one doubt in it whether they are asking about 'n' integers or only a single integer 'n' ? If they are asking about only a single integer's correct position here than we can also use Quick sort in it which also give us O(n) time for a single element.

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

edited
0
Gd explanation ....
0

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)?

+3
@Mamta, b$\neq n^c$, we are setting the b in such a way so that we get O(n) complexity, so if the largest no is $n^3$, we first convert that no in such a base that the time becomes linear, so we take b=n(i.e no of numbers to sort), then no of digits to represent $n^3$ would be $\log_n(n^3)=3$ which would give $O(\log_n(n^3)(n+n))=O(n)$
+1
Thanks @Sukannya :)
0
Is Radix sort and Counting sort are in the syllabus of gate 2019?
0

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(log10k)=3.  849 <= n5 where c=5 (849<=3125).

O(nclog10n) = 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..?

0

correction : "why you* took b=5 then " 0

If based on what i said is correct..

then will you explain me how it will be sorted using base as 849 ( its weird so i haven't tried but i am curious how it will sort and will it sort correctly so help me out on your example only )

As no comparison based sort can ever do any better than nlogn (Unless in special cases) a,b,c are eliminated. nlogn is lower bound for comparison based sorting.

As Radix sort is not comparison based sort (it is counting sort) D is correct !
–1
shouldn't it include quick sort also?here it is asked to sort 1 element i.e. 'n' in the range 1 to $n^3$.
0
what would be the complexity of the radix sort in this case?
+1
time complexity of radix sort is theta ((n+k)d)
0
counting sort will take theta(n^3)??

Radix sort complexity is O(wn) for n keys which are integers of word size w.
+5

Here word size = ( 1 to n3) . = 3 log10(n) ...

So again time complexity would be = n log n .

Correct me if I am wrong ..

+2
I think @Akash gave correct reason. Because no comparison based sorting in all cases(best, avg., worst) gives O(n) complexity
0
Nice explanation.
0
nice

1