# GATE2010-12

4.7k views

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

$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
0
Best approach nice explanation
0
Superb ....
0
I have a query why n is replaced by 10^k?
1
@hemchandra:- A takes $.0001n^2$,means for n input it takes this time. But our input is $10^k$,n=$10^k$
6
@Arjun sign ,i think the equation should be strict inequality,because if for some value they come equal then we may or may not prefer B over A
0
n^2 is asymptotically bigger than (n log n ) so obviously after some point of time n^2 will overtake.   (n log n ).... they have asked the minimum value at which this overtake will happen
0

sir prefer b means b should take less time than a  then is fiirst condition true sir?

10nlog10>=0.0001n2  why can't we consider this one?

0
You make our life easy :) . Thank you Arjun sir

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.

0
Thanks

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

1 vote
We have to find the first value for which k*(0.0001n^2) comes out to be greater than 10logn, taking value of n as 10^4.

The answer comes out to be b), when k=10. Before that it is smaller for every value.
0

Actually that was a typo in question- n is 10k and not 4. Sorry, now corrected.

First take 5.

A's required time=$0.0001*(10^5)^2$=$10^6$

B's required time=$10*10^5*\log_{10}10^5$=$10^6*5$

So, clearly 5 is not the answer .

Take 6

A's required time=$0.0001*(10^6)^2$=$10^8$

B's required time=$10*10^6*\log_{10}10^6$=$10^7*6$

## Related questions

1
3.1k 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 neither hockey nor football is: $2$ $17$ $13$ $3$
Suppose computers $A$ and $B$ have $IP$ addresses $10.105.1.113$ and $10.105.1.91$ respectively and they both use same netmask $N$. Which of the values of $N$ given below should not be used if $A$ and $B$ should belong to the same network? $255.255.255.0$ $255.255.255.128$ $255.255.255.192$ $255.255.255.224$