edited by
12,590 views
45 votes
45 votes

Two alternative packages $A$ and $B$ are available for processing a database having $10^k$ records. Package $A$ requires $0.0001 n^2$ time units and package $B$ requires $10n\log_{10} n$ time units to process $n$ records. What is the smallest value of $k$ for which package $B$ will be preferred over $A$?

  1. $12$
  2. $10$
  3. $6$
  4. $5$
edited by

6 Answers

Best answer
120 votes
120 votes
$10n \log_{10} n ≤ 0.0001n^2$

$\implies 10 \times10^k \log_{10} 10^k \leq 0.0001 (10^k)^2$

$\implies 10^{k+1} k \leq 0.0001 \times 10^{2k}$

$\implies k \leq 10^{2k -k -1 - 4}$

$\implies k \leq 10^{k-5}$

Trying the values, $5$ doesn't satisfy this but $6$ satisfies.

Correct Answer: $C$
edited by
10 votes
10 votes

for large values of k, A will take more time then B

A>>>>B (for large k)

so, for large k, B always prefer 

but in question they are asking what is the smallest value of k that B prefer 

let take for k=5,   A-> 106  and  B->5*106   (A<B) so A will prefer

           for k=6,   A-> 108  and  B->6*107   (A>B) so B will prefer

(C.) is the correct option.

5 votes
5 votes

n=10^k

A=  $\frac{10^2^k}{10^4}$

B=  10.10^k log10^k   (here log base is 10)

B= 10.10^k.k

  =k.10.10^k <  $\frac{10^2^k}{10^4}$

 = k< $\frac{10^2^k}{10^4.10.10^k}$

=K <  $\frac{10^k}{10^5}$

NOW CHEK IF K=5

= 5<$\frac{10^5}{10^5}$

= 5 < 1-------------------- NO SO THIS IS NOT POSSIBLE. 

= LETS TAKE K= 6

=6<$\frac{10^6}{10^5}$

=6<10

K=6  SO OPTION C OUR ANS.yes

4 votes
4 votes

time for n records of package A = 0.0001 * n^2
time for k records of package A = 0.0001 * (10^k)^2 = 10 ^(-4) * 10 ^ 2k = 10 ^ (2k -4)

time for n records of package B = 10 * n * logn ( log is base 10)
time for k records of package A = 10 * 10 ^ k * log (10 ^k) = 10 ^ (k + 1) * log 10 ^ k = 10 ^ (k +1) * k
package b preffered over a -> time for a > time for b

10 ^ (2k -4) > k * 10 ^(k +1)

k=5 -> 10^6 > 5 * 10^6 (false)
k =6 -> 10^8 > 6 * 10 ^7 (true)
 

Answer:

Related questions

12 votes
12 votes
5 answers
1
go_editor asked Sep 30, 2014
6,497 views
$25$ persons are in a room. $15$ of them play hockey, $17$ of them play football and $10$ of them play both hockey and football. Then the number of persons playing neithe...
7 votes
7 votes
1 answer
2
go_editor asked Sep 30, 2014
3,877 views
Choose the most appropriate word from the options given below to complete the following sentence:If we manage to __________ our natural resources, we would leave a better...
41 votes
41 votes
2 answers
4