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)4,000,000 B)1,000,000 C)1,000 D)16

Question

Quizplus · Accepted Answer

Selection sort has a time complexity of O(n^2), meaning the time it takes to sort the elements grows quadratically with 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, because (1,000,000 / 1,000)^2 = 1,000^2. Therefore, it will take 4 * 1,000^2 = 4,000,000 seconds.

Selection Sort Has O(n2) Complexity

Selection Sort Has O(n²) Complexity