Please help me to solve this - Given an (unsorted) array of n elements, can we Sort them in O(n) time?
it depends. radix and counting sort work in O(n) but they require special constraints on input like the numbers are in range 1 to n etc.there are some other sorts but they require special hardware requirements. for practical purposes O(nlogn) in worst case is the best we know.
For details check out the wikipedia page.
Pls upvote this ans if you find it useful. For queries comment below.
No, there is no algorithm that sorts in O(n) time unless, the array is sorted or almost sorted.
In that case algorithms like Tim Sort and Bubble Sort give a best-case time complexity of O(n)
In general no. O(n\log(n)) is a tight bound (assuming element comparison in constant time). But for special cases it is possible. If you have an array of integers bounded by O(n) or a string (considering it to be an array of chars) you can use Counting sort.
1 Like