Sorting

Question

A machine took 200 sec to sort 200 names,using bubble sort.In 800 sec,it can approximately sort ?
a. 400 names b. 800 names c. 750 names d. 850 names

Comments

It's not Hashing..

Answer 1

Using Bubble sort total number of comparisons $\frac{n(n-1)}{2}$ or $O(n^{2})$

So for sorting 200 names bubble sort makes $200^{2}$ comparisons in worst case.To sort 200 names bubble sort is taking 200 sec or we can say 40000 comparisons takes 200 sec.

Now we have compute how many names will sort in 800 sec.

So $n^{2}=\frac{40000\times 800}{200}$

So $n$=400 names will sort in 800 sec.

 

---

Alternatively

For 200 names =200*199/2

                        =19900 comparison

So 19000 c=200 sec

$\frac{n(n-1)}{2}$=800 sec

$\frac{n(n-1)}{2}$=79600

So $n$=400

Comments

19900 comparison takes 200 sec

1c should take 200/19900 secs

---

yes

---

@ManojK, How have u got d answer as 160000?? Please explain this. Rest is stil understandable. :)

---

Ans is 400 names.

Answer 2

To Find solution these kind of quetion u have to know What is the time complexity of given algorithm 

like in above quetion Bubble  sort

Best case = O(n²) without modified

Worst case = O(n²)

Now take quetion If he say how many time to sort 800 names.

200 sec to sort 200 names using bubble sort.

Bubble sort take for n names = O(n²) 

here take 200 = 200sec

but in actual it take O(200²)= 40000sec

now simple math apply inplace of 40000/200 = 200 it take 200 sec

for 800 bubble sort actualy take o(800²)= 160000 sec

But like above divide ans by 200 so 640000/200= 3200sec

 

 

but he is asking for how many name sort in 800 sec ..

so to in 200 sec= 200 name 

but actualy it want 40000sec

in quetion 1 sec= 1name

wat is relation b/w program and actual algorithm time complexity

so 1 sec = 200/40000= 1/200 name 

so  in 800 sec= O(n²)

since 800 sec= O(n²)/200

= 160000= O(n²)

take log both side

u get n= 400

Comments

Actually u have mistaken to understand the qus

here it is asking in 800 sec how many names will sort???

so qus will be solved like this

(200)^2=200 sec

n^2=800 sec

n^2=160000

n=400

Ans will be 400 name will sort 800 sec using bubble sort

---

thanks for make me correct about quetion.

---

ok

Answer 3

we know the time complexity of bubble sort is O(n²).

where n=no of elemnts given

A/Q

200 elemnts are required to be sorted in 200sec

i.e 200*200(40000) comparision are req to sort in 200 sec

1 comparision is requies 1/200sec.........................(A)

let there are k² comparsion are req for k elemnt that can be sorted in 800 sec

therefore,

from eqation A

k²  *1/200=800

on soving we get k=400  ans