search
Log In
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$
in Algorithms
edited by
4.7k views

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 by
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.yes

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$
asked Sep 30, 2014 in Numerical Ability jothee 3.1k views
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
asked Sep 30, 2014 in Verbal Ability jothee 1.3k views
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$
asked Sep 30, 2014 in Computer Networks jothee 4.9k views
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
asked Sep 29, 2014 in Operating System jothee 4.6k views
...