# 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.8k 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.

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
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

## Related questions

1
677 views
Suppose we have a heap containing n = 2k elements in an array of size n', and suppose that we repeatedly extract the minimum element, n' times, never performing insertions. To make the heap space efficient, we move the heap over to an array of size 2j whenever an extraction ... heap of n elements? (Ignore the Θ(n log n) cost from the heapify operations themselves. Θ(n) Θ(2n) Θ(logn) Θ(nlogn)