edited by
16,516 views
39 votes
39 votes

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
edited by

5 Answers

Best answer
55 votes
55 votes

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/

edited by
16 votes
16 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 !
11 votes
11 votes
Answer: D

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

Related questions

37 votes
37 votes
10 answers
1
Kathleen asked Sep 12, 2014
17,327 views
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______
28 votes
28 votes
1 answer
2
42 votes
42 votes
8 answers
3
Kathleen asked Sep 13, 2014
14,283 views
Which of the following regular expression identities is/are TRUE?$r^{(^\ast)} =r^\ast$$(r^\ast s^\ast)=(r+s)^\ast$$(r+s)^\ast = r^\ast + s^\ast$$r^\ast s^\ast = r^\ast+s^...
24 votes
24 votes
4 answers
4
Kathleen asked Sep 13, 2014
9,908 views
Which of the following is/are a tautology?$a \vee b \to b \wedge c$$a \wedge b \to b \vee c$$a \vee b \to \left(b \to c \right)$$a \to b \to \left(b \to c \right)$