Multiple choice technology

If I am given an infinite memory space, which algorithm will I use to sort a set of natural numbers with best time complexity?

  1. Merge sort

  2. Heap sort

  3. Counting sort

  4. Bubble sort
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

With infinite memory, Counting sort achieves O(n + k) time complexity where k is the range of values. Since we have infinite memory and are sorting natural numbers, Counting sort is optimal. Comparison sorts like Merge sort and Heap sort are O(n log n), while Bubble sort is O(n^2).

Keep practicing — related questions