Selection sort has O(n²) complexity. If a computer can sort 1,000 elements in 4 seconds, approximately how many seconds will it take the computer to sort 1,000 times that many, or 1,000,000 elements? A) 16 B) 1,000 C) 1,000,000 D) 4,000,000

Question

Quizplus · Accepted Answer

Selection sort has a time complexity of O(n^2), meaning the time taken is proportional to the square of the number of elements. If sorting 1,000 elements takes 4 seconds, sorting 1,000,000 elements (which is 1,000 times more) will take 1,000^2 times longer, which is 1,000,000 times longer, resulting in 4,000,000 seconds.

Selection Sort Has O(n2) Complexity

Selection Sort Has O(n²) Complexity