45 votes 45 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$ Algorithms gatecse-2010 algorithms time-complexity easy + – go_editor asked Sep 29, 2014 edited Nov 24, 2017 by kenzou go_editor 12.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes 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. mBee answered Nov 5, 2014 mBee comment Share Follow See 1 comment See all 1 1 comment reply Arjun commented Nov 5, 2014 reply Follow Share Actually that was a typo in question- n is 10k and not 4. Sorry, now corrected. 0 votes 0 votes Please log in or register to add a comment.
0 votes 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) Ramij answered Oct 20, 2018 Ramij comment Share Follow See all 0 reply Please log in or register to add a comment.