retagged by
744 views
1 votes
1 votes
"A" sort a particular dataset of size n using merge sort in 640 msec, "B" uses the same algorithm on dataset of size 16, it takes 256 msec to sort them. what is size of data set used by "A"
A. 32
B. 64
C. 128
D. None of above
retagged by

3 Answers

3 votes
3 votes

"A" sort a particular dataset of size n using merge sort takes time =  640 msec, 

we know that time complexity of merge sort = O(nlogn) = c1. nlogn

so 640 = c1. nlogn                           -(1)

"B" uses the same algorithm on dataset of size 16 takes = 25 msec

256 = c1. nlogn​​​​​​​  [here we know n = 16] 

256  = c1. 16 log16

​​​​​​​c1= 4 

Put value of c1= 4 in (1)

We get answer as 32.

0 votes
0 votes

Given :

  1. $c \times 64\log_{2}64 == 256$, &&
  2. $c \times n \log_{2}n == 640$

Required: $n$.

Proceed as :

$\frac{c \times n \log_{2}n}{c \times 16log_{2}16} == \frac{640}{256}$

or $n \log_{2}n == 160$

$\implies n == 32$

i.e. Option $(A)$

 
Answer:

Related questions

0 votes
0 votes
1 answer
2
2 votes
2 votes
4 answers
3
Ramij asked Dec 20, 2018
2,290 views
Suppose there are 4 sorted list of 16 elements each. If we merge these lists into a single sorted list of 64 elements. The key comparisons that are needed in the worst ca...
1 votes
1 votes
1 answer
4
Hira Thakur asked Aug 14, 2016
264 views
given 2 sorted list of size m and n the number of comparison are required in worst case by merge sort algorithsm is1.mn2.max(m,n)3.min(m,n)4.m+n-1