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
| 6.3k views

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
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