7 votes 7 votes Which of the following is best running time to sort $n$ integers in the range $0$ to $n^2-1$? $O(\text{lg } n)$ $O(n)$ $O(n\text { lg }n)$ $O(n^2)$ Algorithms ugcnetcse-june2019-paper2 sorting + – Arjun asked Jul 2, 2019 edited Jul 24, 2019 by Lakshman Bhaiya Arjun 3.3k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Abhisek Tiwari 4 commented Jul 3, 2019 i edited by Abhisek Tiwari 4 Jul 11, 2019 reply Follow Share Best case of Insertion/Bubble sort (When Numbers are already sorted). i.e O(n) 0 votes 0 votes Sanjay Sharma commented Jul 11, 2019 reply Follow Share can we sort in lgn time ? at best it may be O(n) 2 votes 2 votes Vishal_kumar98 commented Nov 25, 2021 reply Follow Share Nothing has been told about whether they are sorted or unsorted sequence. 0 votes 0 votes Sanjay Sharma commented Nov 25, 2021 reply Follow Share sorting in linear time (like radix,count etc ) can sort any unsorted array in O(n) time 0 votes 0 votes Please log in or register to add a comment.
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/ Aneep Raj Agrawal answered Jul 29, 2019 Aneep Raj Agrawal comment Share Follow See all 2 Comments See all 2 2 Comments reply rish1602 commented Jul 15, 2021 i edited by rish1602 Aug 9, 2021 reply Follow Share @Sanjay Sharma But why 0(n)…..I mean in the question its not mentioned that elements are sorted or unsorted. So why are we not taking the average case of (nlogn) i.e. option c 0 votes 0 votes Sanjay Sharma commented Nov 25, 2021 reply Follow Share sorting in linear time (like radix,count etc ) can sort any unsorted array in O(n) time 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes option B) O(n) using Radix sort. Sanandan answered Sep 9, 2020 Sanandan comment Share Follow See 1 comment See all 1 1 comment reply rish1602 commented Jul 15, 2021 reply Follow Share But why 0(n)…..I mean in the question its not mentioned that elements are sorted or unsorted. So why are we not taking the average case of (nlogn) i.e. option c 0 votes 0 votes Please log in or register to add a comment.
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). DAWID15 answered Dec 21, 2021 DAWID15 comment Share Follow See all 0 reply Please log in or register to add a comment.