edited by
3,275 views
7 votes
7 votes

Which of the following is best running time to sort $n$ integers in the range $0$ to $n^2-1$?

  1. $O(\text{lg } n)$
  2. $O(n)$
  3. $O(n\text { lg }n)$
  4. $O(n^2)$
edited by

3 Answers

0 votes
0 votes

Best time complexity is O(n). 

 

Refer below link for reference 

 

https://www.geeksforgeeks.org/sort-n-numbers-range-0-n2-1-linear-time/

 

 

0 votes
0 votes
option B) O(n) using Radix sort.
0 votes
0 votes

here nothing is mentioned if the array is already sorted or not. However if we use a non-comparison based sorting algorithm like counting sort then the complexity will be O(n).

Answer:

Related questions

2 votes
2 votes
2 answers
1
Arjun asked Jul 2, 2019
1,631 views
Match List-I with List-II:$$\begin{array}{|c|c|c|c|} \hline {} & \text{List-I} & {} & \text{List-II} \\ \hline (a) & \text{Prim’s algorithm} & (i) & O(V^3 \log V) \\ \h...
1 votes
1 votes
1 answer
3
Arjun asked Jul 2, 2019
1,851 views
Which of the following is application of depth-first search?Only topological sortOnly strongly connected componentsBoth topological sort and strongly connected components...
3 votes
3 votes
2 answers
4