Question

The minimum possible time complexity to sort \(n\) integers in the range [1, \(n^2\)] is _______ .

• A. O(n)
• B. O(n\log n)
• C. O(n\(^2\))
• D. O(\(\log n\))

Hint:

For sorting a known range of values, non-comparison-based algorithms such as Counting Sort or Radix Sort can achieve linear time complexity.

Answer 1

The Correct Option is A

When sorting integers in the range [1, \(n^2\)], the minimum time complexity is \(O(n)\), achieved by using non-comparison-based algorithms like Counting Sort or Radix Sort. These algorithms can exploit the known range of values for sorting. Comparison-based algorithms like Merge Sort or Quick Sort have a lower bound of \(O(n \log n)\).