retagged by
678 views

2 Answers

3 votes
3 votes

 We are using quick sort here.

 To sort 1000 names no of comparsion=$1000log_{2}\left ( 1000 \right )$

To sort 100 names no of comparsion=$100log_{2}\left ( 100 \right )$

So $1000log_{2}\left ( 1000 \right )$ comparison can be done in 100 sec.

Let the minimum time to sort  100 names is $x sec$

                      $1000log_{2}\left ( 1000 \right )$=$100 sec$

                      $100log_{2}\left ( 100 \right )$=$x sec$

                      So $x $=$\frac{100log_{2}\left ( 100 \right )\times100 sec}{1000log_{2}\left ( 1000 \right )}$

                      So $x $=$6.67 sec$

Minimum time needed to sort 100 names is 6.67 sec.

edited by
0 votes
0 votes
The best case time complexity of is O(nlogn)

now if say T(n) is the real time complexity of a program and if T(n)<=c.F(n) , then we say that T(n)=O(F(n))..

as they have told minimum therefore it is the best case

now 100<=c.1000.log[base2]1000

we get c as something ≈0.010034

now for 100 names it will be ≈ 0.010034.100.log[base 2]100

≈6.666445308.....≈6.7sec

Related questions

31 votes
31 votes
6 answers
1
Kathleen asked Sep 18, 2014
19,272 views
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...
0 votes
0 votes
0 answers
3
mdboi asked Oct 29, 2022
288 views
Hello, i have a algorithm and i want to prove it with induction how can i do that ?Also i want to worst case run time analyze but i am not very good please help me please...
3 votes
3 votes
1 answer
4
Sanjay Sharma asked Feb 20, 2018
1,039 views
An array A is of length n has log( n) distinct numbers.What is the time complexity of sorting A by best comparison based algorithm ?