The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
2.4k 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$
asked in Algorithms by Veteran (103k points)
edited by | 2.4k views

6 Answers

+52 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.
answered by Veteran (359k points)
edited by
0
Best approach nice explanation
0
Superb ....
0
I have a query why n is replaced by 10^k?
0
@hemchandra:- A takes $.0001n^2$,means for n input it takes this time. But our input is $10^k$,n=$10^k$
+4
@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
+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

answered by Junior (637 points)
+4 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.

answered by Active (1.1k points)
0
Thanks
+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)
 

answered by (45 points)
+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.
answered by (21 points)
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)
answered ago by (101 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,065 questions
47,661 answers
147,308 comments
62,381 users