The Gateway to Computer Science Excellence
+8 votes
6.3k views

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

  1. 50.2 sec
  2. 6.7 sec
  3. 72.7 sec
  4. 11.2 sec
 
 
 
in Algorithms by (73 points) | 6.3k views

2 Answers

+17 votes
Best answer
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
by Veteran (431k points)
selected by
–1

lg 100=2 0.01*100*2=2

then how come 0.01 * 100 * lg 100 = 6.7 ?????

0
$\lg$ is used for $\log_2$.
0
Ok Thanks
0
how when n=1000 c=0.01??? pls solve m not getting c=.01
+13 votes
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
by Active (1.3k points)
0
i have a doubt . nlogn .. why it is  base 10 ( 1000log (base10)1000 ) . it should be base 2( 1000log (base2)1000 )
+1
Yes. base should be 2 but answer won't change as the log term gets cancelled out.
+2
Arjun sir , for simplification we can use base 10 , because value is multiple of 10.
can we use for other similar problems??
0
yes, you can do that..
0
thnks sir
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
198,262 comments
104,976 users