GATE CS 2010 Q12 — Asymptotic Worst Case Time and Space Complexity

We are given the database size $n = 10^k$.

The time required by the two packages to process $n$ records is:

• Package A: $T_A(n) = 0.0001 n^2 = 10^{-4} n^2$
• Package B: $T_B(n) = 10 n \log_{10} n$

Package $B$ is preferred over Package $A$ when it takes strictly less time, i.e.,

Substitute the expressions for $T_A(n)$ and $T_B(n)$:

Since $n = 10^k \ge 1$, we can divide both sides by $n$:

Now, substitute $n = 10^k$ into the inequality:

Let us test the integer values of $k$ starting from the options:

• For $k = 5$: $$10(5) < 10^{5-4} \implies 50 < 10 \quad \text{(False)}$$
• For $k = 6$: $$10(6) < 10^{6-4} \implies 60 < 100 \quad \text{(True)}$$

Thus, the smallest integer value of $k$ for which Package $B$ is preferred over Package $A$ is $6$.