# GATE2010-12

24 votes
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

## 6 Answers

77 votes

Best answer
$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
5 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.

0
Thanks
4 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.

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

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.

0 votes
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$

So answer is (c)
Answer:

## Related questions

9 votes
5 answers
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$
5 votes
2 answers
2
1.3k 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 planet for our children. uphold restrain cherish conserve
25 votes
4 answers
3
4.9k views
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$
26 votes
2 answers
4
4.6k views
Which of the following statements are true? Shortest remaining time first scheduling may cause starvation Preemptive scheduling may cause starvation Round robin is better than FCFS in terms of response time I only I and III only II and III only I, II and III