If algorithm \(𝐴\) and another algorithm \(𝐵\) take \(log_2(𝑛)\) and…
2020
If algorithm \(𝐴\) and another algorithm \(𝐵\) take \(log_2(𝑛)\) and \(\sqrt{n}\) microseconds, respectively, to solve a problem, then the largest size \(𝑛\) of a problem these algorithms can solve, respectively, in one second are ______ and ______.
Answer: B. \(2^{10^6}\) and \(10^{12}\) — For a running-time function T(n) measured in microseconds, the largest problem size solvable inside a fixed time budget B is the largest n for which T(n) ≤ B.…
- A.
\(2^{10^n}\)and\(10^6\) - B.
\(2^{10^6}\)and\(10^{12}\) - C.
\(2^{10^6}\)and\(6.10^{6}\) - D.
\(2^{10^6}\)and\(6.10^{12}\)
Attempted by 295 students.
Show answer & explanation
Correct answer: B
For a running-time function T(n) measured in microseconds, the largest problem size solvable inside a fixed time budget B is the largest n for which T(n) ≤ B. When T increases strictly with n, this bound is found by inverting T on both sides of the inequality — exponentiating undoes a logarithm, and squaring undoes a square root.
One second equals 106 microseconds, so B = 106.
Algorithm A takes log2(n) microseconds, so its constraint is log2(n) ≤ 106. Exponentiating both sides with base 2 removes the logarithm, giving n ≤ 210^6.
Algorithm B takes √(n) microseconds, so its constraint is √(n) ≤ 106. Squaring both sides removes the square root, giving n ≤ 1012.
Substituting each bound back in confirms the fit: log2(210^6) equals 106, exactly the time budget, so 210^6 is the largest n algorithm A can handle in one second; and √(1012) equals 106, exactly the time budget, so 1012 is the largest n algorithm B can handle in one second.
Answer: 210^6 and 1012.
A video solution is available for this question — log in and enroll to watch it.