Register

Algorithm

• edited by
1,120 views
0 0 votes

What is the right answer?

Insertion sort: takes $10 \mathrm{n}^{2}$ to sort n times. Merge sort: take 100 nlogn to sort n times. Consider a faster computer A running insertion sort against a slower computer B running merge sort; Both must sort an array of one million ( $\mathrm{n}=10^{\circ}$ ) numbers. Suppose computer $A$ executes 10 billion ( $10^{10}$ ) instruction per second. Computer B executes hundred million $\left(10^{8}\right)$ instruction per second. So computer A is 100 times faster than computer B. Which computer will run the corresponding sorting program faster and by how much faster?

  1. Computer A will run faster by 50 times
  2. Computer B will run faster by 50 times
  3. Computer A will run faster by 100 times
  4. Computer B will run faster by 100 times

1 Answer

0 0 votes

Right answer is B

n= 10^6.                                                                                             (given)

-------------------------------------------------------------------------------------------------

insertion sort takes 10*n*n  units of time for n instructions.             (given)

=> insertion sort takes 10 * 10^6 * 10^6 units of time  for 10^6 instructions.

=> insertion sort takes 10^13 units of time  for 10^6 instructions.

=> insertion sort takes 10^7 units of time  for 1 instruction.

=> 1 instruction in 10^7 units of time..................................................(i)

-------------------------------------------------------------------------------------------------

merge sort takes 100*n*log n  units of time for n instructions            (given)

=> merge sort takes 100*10^6*log 10^6 units of time for 10^6 instructions.

=> merge sort takes 10^8* 19.931 units of time for 1 instruction.

=> 1 instruction in 10^8* 19.931 units of time ....................................(ii)

--------------------------------------------------------------------------------------------------

A executes 10^10 instructions in 1 second                                            (given)

=> 1 instruction in 1/10^10 second......................................................(iii)

-------------------------------------------------------------------------------------------------------

B executes 10^8 instructions in 1 second                                              (given)

=> 1 instruction in 1/10^8 second........................................................(iv)

------------------------------------------------------------------------------------------------------

computer A  runs insertion sort                                                           (given)

=> for 1 instruction resultant time will be   = 1/10^10  * 10^7          ( from (i) and (iii) )

                                                                    = 1000 second 

-------------------------------------------------------------------------------------------------------

computer B runs merge sort.

=> for 1 instruction resultant time will be   = 1/10^8 *10^8* 19.931 ( from (ii) and (iv) )

                                                                    = 19.931 second

                                                                    = 20 second                      (approx)

-------------------------------------------------------------------------------------------------------

speed of B/ speed of A

= time of A for 1 instruction / time of B for 1 instruction    ( since speed is inversely proportional to time)

= 1000 sec / 20  sec

= 50

Hence, B is 50 times faster than A

Voting & Accepting an answer helps improve the community
← Previous · MadeEasy Test Series...Next → · uppcl_2018
← Previous in category · general doubtNext in category → · Time complexity1
Position:
Show:

Related questions

0 0 votes
2 answers 2 answers
984
984 views
Arnabi asked Jan 28, 2017
984 views
Merge sort
3:51 AMVoLTE$35 \%$GATE Mock Test 1All QuestionQuestion: 35Essay Paragraph undefinedQuestionlist of $n$ strings, each of length $n$ is sorted into alphabetical order, usi...
1 1 vote
1 1 answer
2.1k
2.1k views
rahul sharma 5 asked Mar 9, 2018
2,136 views
Merge sort algorithm
Consider the modified merge sort where we divide array into 5 equal sub arrays instead if 2(as in standard merge sort).What is the time complexity if modified merge sort?...
1 1 vote
1 1 answer
603
603 views
Çșȇ ʛấẗẻ asked Aug 28, 2016
603 views
Explain why n>43 ??? #Algo
Suppose we are comparing implementations of insetion sort and merge sort on the same machine. For inputs of size $n$, insertion sort runs in $8 n^{2}$ steps, while merge ...
1 1 vote
1 1 answer
88
88 views
lks_07 asked Jul 9
88 views
Merge sort doubt
for optimized merge sort we can say : It is possible to modify the standard algorithm to check if the last element of the left half is less than or equal to the first ele...