The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 votes

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.....n^3]$ in $O(n)$ time

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

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.

+14 votes

Best answer

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/

+11 votes

Answer :-> D

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 !

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 !

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.8k
- Digital Logic 2k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.8k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 940
- Others 1.2k
- Admissions 320
- Exam Queries 409
- Tier 1 Placement Questions 17
- Job Queries 52
- Projects 8

34,170 questions

40,846 answers

115,882 comments

39,703 users