search
Log In
6 votes
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.
 
in Algorithms 1.8k views

2 Answers

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

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

Related questions

3 votes
2 answers
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)
asked Dec 29, 2016 in Algorithms Akriti sood 677 views
3 votes
1 answer
2
517 views
Consider an array A' with 2m elements. The elements in odd position are sorted in non-increasing order that is A[1] >= A[3] >= A[5]......A[2m-1] The elements in even position are sorted in non-decreasing order, that is A[2]<= A[4] <= A[6].....A[2m ... i thought answer would be B,cuz then O(n) time will be taken but answer is D.how can we apply binary search on odd and even seperatly..pls guide me
asked Dec 26, 2016 in DS Akriti sood 517 views
1 vote
1 answer
3
833 views
There are 200 computers in a lab which are attached to an ethernet 10 Mbps with a coaxial cable of 1500m .The packets are 800 bits long. The propagation speed is 2*10^8 m/sec. On avg how many packets can each computer send per second ? Options 1) 42 packets/sec 2) 44 packets/sec 3) 62 packets/sec 4) None
asked Apr 16, 2015 in Computer Networks Pradyumna Paralikar 833 views
2 votes
1 answer
4
689 views
Consider a system such that the number of clock cycles for a polling operation (including transferring to the polling routine, accessing the device and restarting the user program) is 400 cycles, and that the processor executes with a 500 MHz clock. Determine the fraction of CPU consumed when the mouse must be polled 30 times per second. •0.002 % •0.02 % •0.2 % •None of these
asked Jul 20, 2015 in CO and Architecture resuscitate 689 views
...