Packages A,B process n=10k database records. A needs 0.0001n² time; B needs 10n 10n. Find the smallest integer k for which B is faster.

GATE 2010 CS (CS1) – Question 22

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

Packages A,B process $n=10^k$ database records. A needs 0.0001n² time; B needs $10n\log_{10}n$. Find the smallest integer k for which B is faster.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 6

Explanation

B is preferred when 10×10ᵏ×k < 10²ᵏ⁻⁴, equivalently k<10ᵏ⁻⁵. At k=5 this is 5<1, false; at k=6 it is 6<10, true. Smaller positive integer k also fail. Thus k=6, C.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2015 CS (CS2) Q16 – An unordered list contains n distinct elements. How many comparisons are needed to find…
GATE 2015 CS (CS2) Q26 – Decision problem Q1 reduces in polynomial time to 3-SAT, and 3-SAT reduces in polynomial…
GATE 2015 CS (CS3) Q20 – For i=0n i3=X, consider I (n4), II (n5), III O(n5), IV (n3). Which may replace X?
GATE 2015 CS (CS3) Q37 – Worst-case mergesort takes 30 seconds for input size 64. Which best approximates the…
GATE 2015 CS (CS3) Q41 – L1≤pL2, L3≤pL2 and L2≤pL4. Which are guaranteed? I: L4∈P implies L2∈P. II: L1∈P or L3∈P…
GATE 2015 CS (CS3) Q64 – For positive integer n, f(n)=n and g(n)=n1+ n. Which hold? I: f=O(g). II: f=Ω(g).

All Asymptotic Analysis and Time/Space Complexity questions →