18,284 views
1 votes
1 votes
a machine took 200 sec to sort 200 names using bubble sort . in 800 sec it can approx sort how many names

a)400  b)800 c)750  d)850

2 Answers

Best answer
6 votes
6 votes

Option A is correct i.e, 400

For sorting 200 names bubble sort makes 200 * 199/2 = 19900 comparisons.So,the time needed for 1 comparison is 200 sec approx.In 800 sec it can make 80,000 comparisons.We have to find n,such that n(n-1)/2=80,000. solving n is approx 400.

200 sec for 200 records
200 <= c * [200]^2
c = 1/200
in 800 sec, records, n = ?
800 <= [1/200]*[n]^2
n = 400

OR

800 is 4 x 200. Bubble sort is O(n*n), so on average you can sort twice as many items in 4 times the time, so the expectation is 400, on average, if 200 was an average case.

selected by
2 votes
2 votes

200 seconds to sort 200 items.

Total comparisons for 200 items = 200 * (200-1)/2 = 19900

19900 comparisons are done in 200 seconds. Therefore in 1 second 19900/200 comparisons are done.

So total comparisons in 800 seconds= (19900/200) * 800 = 79600

Lets take number of items to be sorted in 800 seconds = x

So , Number of comparisons for x items in 800 sec = 79600

x(x-1) / 2= 79600

x= 399 , therefore ans is 399 which is approximately 400.

Related questions

2 votes
2 votes
1 answer
1
Mak Indus asked Dec 18, 2018
5,518 views
How many passes of bubble sort are required to sort the following sequence (Pass is counted only when at least one swap is performed in the bubble sort pass)? ...
1 votes
1 votes
1 answer
2
PriDix asked Feb 26, 2017
1,629 views
A machine takes 200 second to sort 200 names, using bubble sort . In 800 seconds , it can approximately sort how many names?
0 votes
0 votes
1 answer
4
Bharani Viswas asked May 17, 2016
536 views
m trying to understand a few sorting algorithms, but I'm struggling to see the difference in the bubble sort and insertion sort algorithm.in a particular case where the e...