Question

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.

 

Answer 1

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.

Comments

1 rupee

and thank u sir i got ur point

---

yes, but that was a typo from me.. :(

---

yes sir

Answer 2

The question seems to be wrong.It should be http://stackoverflow.com/questions/28000548/time-taken-to-sort-array-when-cpu-operates-on-108-operations-sec