ISRO2015-12

Question

A machine needs a minimum of $100$ sec to sort $1000$ names by quick sort. The minimum time needed to sort $100$ names will be approximately

• A. $50.2$ sec
• B. $6.7$ sec
• C. $72.7$ sec
• D. $11.2$ sec

 

 

 

Answer 1

Running time of quick sort = c n lg n

For n = 1000, we get

100 = c * 1000 * lg 1000 => c = 0.01

So, for n = 100, we get running time = 0.01 * 100 * lg 100 = 6.7

Comments

how when n=1000 c=0.01??? pls solve m not getting c=.01

---

ANS. (B)

---

Thank youu so much

 

Answer 2

min no of comparison for quick sort = nlogn

so to sort 1000 names 1000*3 ie 3000 comparisons are needed.

For 3000 comparisons we need 100s , thus for 1 comparison we need 0.033s

To sort 100 names we need 200 comparisons thus time needed is 0.033*200 s = 6.67 s

Comments

yes, you can do that..

---

thnks sir

---

How we are using comparison as 3k ?

Answer 3

TC of Quick Sort = O(nlogn) = c.nlogn (base = 2)

For, n = 1000,
TC = 100 sec = c (1000 x log1000)
         100 sec = c (1000 x log1024) // log1000 ≈ log1024
         100 sec = c (1000 x 10)
                    c = 0.01 sec

For, n = 100
TC = c (100 x log100)
      = 0.01 (100 x log100) sec
      = 0.01 (100 x log128) sec // log100 ≈ log128
      = 0.01 (100 x 7) sec
      = 7 sec ≈ 6.7 sec

So, option B is correct