GATE CSE 1992 | Question: 02,ix

Question

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
4. Radix sort

Comments

@ManuThakur,

Why are you not including the complexity of conversion in Base b from base 10?

---

Any comparison based sorting requires atleast "nlogn" time. So if n running time is required all options other than c are wrong.

---

Some variation 

Question: You are given an array of $n$ distinct integers. The integers are in the range $[1, n^4]$. What is the worst-case time complexity to sort this array using an optimally configured Radix Sort?

A) $O(n \log n)$

B) $O(n^2)$

C) $O(n)$

D) $O(n^4)$

Solution:

1. Find $b$ (the number of bits). Since the max number is $n^4$, $b = \log_2(n^4) = 4 \log_2 n$.

2. Use the optimal chunk size $r = \log_2 n$ (from Lemma 8.4).

3. Number of passes $d = \frac{b}{r} = \frac{4 \log_2 n}{\log_2 n} = 4$.

4. Time per pass $= \Theta(n + 2^r) = \Theta(n + 2^{\log_2 n}) = \Theta(n + n) = \Theta(n)$.

5. Total time $= d \times (\text{Time per pass}) = 4 \times \Theta(n) = \mathbf{\Theta(n)}$.

   Correct Option: C 

 

Question: A system uses a stable counting sort to implement Radix Sort on an array of $65536$ ($2^{16}$) 64-bit integers. To minimize the time complexity according to Lemma 8.4, what should be the size of the counting array (number of buckets) used in each pass, and how many passes are required?

 

A) Buckets: 65536, Passes: 4

B) Buckets: 256, Passes: 8

C) Buckets: 65536, Passes: 8

D) Buckets: 16, Passes: 4

Solution:

1. We have $n = 2^{16}$ elements and $b = 64$ bits.

2. To minimize time, we choose $r = \log_2 n$.

   $r = \log_2(2^{16}) = 16$ bits per chunk.

3. The number of buckets (size of the counting array) is $k = 2^r = 2^{16} = 65536$.

4. The number of passes is $d = \frac{b}{r} = \frac{64}{16} = 4$ passes.

   Correct Option: A

 

Question: You are given an array of $n$ integers where the maximum integer can be up to $2^{n \log n}$. Which sorting algorithm is asymptotically faster for this specific array: Merge Sort or optimally configured Radix Sort?

 

Solution:

1. Merge Sort Time: Always $\Theta(n \log n)$.

2. Radix Sort Analysis:

   • Find $b$: Since the max number is $2^{n \log n}$, the number of bits $b = \log_2(2^{n \log n}) = n \log n$.

   • Optimal $r$: We set $r = \log_2 n$.

   • Apply Lemma 8.4 formula: $\Theta\left(\frac{bn}{\log n}\right)$.

   • Substitute $b$: $\Theta\left(\frac{(n \log n) \cdot n}{\log n}\right) = \Theta(n^2)$.

3. Conclusion: Radix Sort takes $\Theta(n^2)$ time, whereas Merge Sort takes $\Theta(n \log n)$ time. Therefore, Merge Sort is asymptotically faster in this scenario. This proves Radix sort is not a magic bullet; it fails if the numbers are exponentially large relative to $n$.

Answer 1

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/

Comments

@MiNiPanda 

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

---

@MiNiPanda 

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 )

---

I think yeah the base needs to be increased inorder for radix sort to work faster.
Just like in your example, the previous base was 3 so maximum 3 repetitions was happening but as you tried to take the base down to 5, it increased to 5 repetitions.

Answer 2

Answer :- $D$

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

As Radix sort is not comparison based sort (it is counting sort) So, $D$ is correct !

Comments

counting sort will take theta(n^3)??

---

sushmita

it will take O(n) only.

---

simple and best

Answer 3

Answer: D

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

Comments

Here word size = ( 1 to n³) . = 3 log₁₀(n) ... 

So again time complexity would be = n log n .

Correct me if I am wrong ..

---

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

---

Nice explanation.

---

nice

Answer 4

It would be radix sort.

You can see the explanation at :https://www.geeksforgeeks.org/radix-sort/

Answer 5

Radix Sort can be used here.

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.

Comments

@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

---

https://gateoverflow.in/559/gate1992-02-ix”

---

It has 3 pass and each pass has n elements, i.e. why O(n)

Answer 6

Radix Sort is a non-comparative integer sorting algorithm that sorts numbers by processing individual digits that share the same position and value. It can sort n integers in the range [1, n³] in O(n) time because it uses digit-by-digit counting (using Counting Sort as a subroutine), which runs in linear time when the number of digits is constant.

In contrast, Heap Sort, Quick Sort, and Merge Sort are comparison-based sorting algorithms and therefore have a lower bound of Ω(n log n) on their time complexity.

Therfore ans: D) Radix Sort