The Gateway to Computer Science Excellence
+6 votes
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.
 
in Algorithms by Loyal (6.3k points) | 1.6k views

2 Answers

+11 votes
Best answer
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 by
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
0 votes
by Active (2.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,496 answers
195,489 comments
100,801 users