8,998 views
6 votes
6 votes
Assume that a CPU can process $10^8$ operations per second. Suppose you have to sort an array with $10^6$ elements. Which of the following is true?
 
1. Insertion sort will always take more than 2.5 hours while merge sort will always take less than 1 second.
2. Insertion sort will always take more than 2.5 hours while quicksort will always take less than 1 second
3. Insertion sort could take more than 2.5 hours while merge sort will always take less than 1 second.
4. Insertion sort could take more than 2.5 hours while quicksort will always take less than 1 second.
 

2 Answers

Best answer
12 votes
12 votes
Merge sort complexity is $\Theta(n \lg n)$, and so we need $10^6 \lg 10^6 \approx 20 \times 10^6$ and assuming the constant factor is less than 5, number of instructions would be less than $10^8$ and can be run within a second.

Worst case complexity of insertion sort is $O(n^2)$ and to sort $10^6$ elements it needs $10^{12}$ operations and with $10^8$ operations per second this would need $10^4$ seconds = 2 hours 46 minutes.

Now, best case complexity of insertion sort is $O(n)$. So, "always" in options 1 and 2 make them false.

Similarly worst case of quick sort is $O(n^2)$ and this makes option 4 false.

So, option 3 is the answer.
selected by

Related questions

8 votes
8 votes
2 answers
1
0 votes
0 votes
2 answers
3