1.6k views
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.

| 1.6k views

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.
by Veteran (425k points)
selected
0
@ arjun sir,sanjay  .sorry for the silly question

for insertion sort:10^8 operation can be done in 1 second

and the rest 10^4 operation can be done in next second....i m finding problem here..plz clear
0
$10^{8}$ apples cost 1 rupee, how much does $10^{12}$ apples cost?
0
1 rupee

and thank u sir i got ur point
0
yes, but that was a typo from me.. :(
0
yes sir