GATE CSE 2010 | Question: 12

Question

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$?

• A. $12$
• B. $10$
• C. $6$
• D. $5$

Comments

https://www.youtube.com/watch?v=UpZ7JtcBcz8

Answer 1

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

Comments

how that <= relation came can anyone pls clarify me?

---

@pavansan  when we preffered B over A  ?   when  B's time <= A's time 

 

---

prefer means it takes less time so B<=A

 

Answer 2

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-> 10⁶  and  B->5*10⁶   (A<B) so A will prefer

           for k=6,   A-> 10⁸  and  B->6*10⁷   (A>B) so B will prefer

(C.) is the correct option.

Comments

Thanks

---

simple and elegant.

Answer 3

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.

Answer 4

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 5

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.

Comments

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

Answer 6

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)