10 votes 10 votes 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 $50.2$ sec $6.7$ sec $72.7$ sec $11.2$ sec Algorithms isro2015 algorithms quick-sort + – ish.nit513 asked May 19, 2015 • edited Dec 4, 2022 by Lakshman Bhaiya ish.nit513 10.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 22 votes 22 votes 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 Arjun answered Jun 7, 2015 • selected Jun 7, 2015 by Arjun Arjun comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments naga praveen commented Jun 20, 2016 reply Follow Share Ok Thanks 0 votes 0 votes shweta1920 commented Dec 16, 2017 reply Follow Share how when n=1000 c=0.01??? pls solve m not getting c=.01 0 votes 0 votes princeit07 commented Jun 26, 2021 reply Follow Share ANS. (B) 0 votes 0 votes Please log in or register to add a comment.
13 votes 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 komal07 answered May 19, 2015 komal07 comment Share Follow See all 5 Comments See all 5 5 Comments reply Pranay Datta 1 commented Jun 7, 2015 reply Follow Share i have a doubt . nlogn .. why it is base 10 ( 1000log (base10)1000 ) . it should be base 2( 1000log (base2)1000 ) 0 votes 0 votes Arjun commented Jun 7, 2015 reply Follow Share Yes. base should be 2 but answer won't change as the log term gets cancelled out. 1 votes 1 votes Devwritt commented Jul 2, 2016 reply Follow Share Arjun sir , for simplification we can use base 10 , because value is multiple of 10. can we use for other similar problems?? 2 votes 2 votes Arjun commented Jul 2, 2016 reply Follow Share yes, you can do that.. 1 votes 1 votes Devwritt commented Jul 2, 2016 reply Follow Share thnks sir 0 votes 0 votes Please log in or register to add a comment.