The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 votes

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

- $12$
- $10$
- $6$
- $5$

+66 votes

Best answer

+1

@hemchandra:- A takes $.0001n^2$,means for n input it takes this time. But our input is $10^k$,n=$10^k$

+5

@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

+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-> 10^{6} and B->5*10^{6} (A<B) so A will prefer

for k=6, A-> 10^{8} and B->6*10^{7} (A>B) so B will prefer

(C.) is the correct option.

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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

49,845 questions

54,783 answers

189,420 comments

80,412 users