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

0 votes
0 votes
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.
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,285 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,915 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)$