Project ForgeSign up free
Algorithms
Complexity Analysis
GATE 2010
Hard

Two alternative packages A and B are available for processing a database having 10^k records. Package A requires 0.0001n² time units and package B requires 10n log₁₀n time units to process n records. What is the smallest value of k for which package B will be preferred over A?

  • A12
  • B10
  • 6
  • D5

Explanation

B preferred means 10n·log₁₀n < 0.0001n², i.e. log₁₀n < 0.00001n. With n=10^k, log₁₀n=k, so the condition is k < 0.00001×10^k. Testing k=5: RHS=1, and 5<1 is false. Testing k=6: RHS=10, and 6<10 is true. So the smallest valid k is 6.

Source: GATE CS 2010 (2010)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free