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 ______.
- 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 242 students.
Show answer & explanation
Correct answer: B
One second = 106 microseconds.
For the algorithm that takes log2(n) microseconds: set log2(n) ≤ 106. Therefore n ≤ 2^{10^6}, so the largest n that fits in one second is 2^{10^6}.
For the algorithm that takes sqrt(n) microseconds: set sqrt(n) ≤ 106. Squaring both sides gives n ≤ (10^6)^2 = 10^{12}, so the largest n is 10^{12}.
Answer: 2^{10^6} and 10^{12}.
A video solution is available for this question — log in and enroll to watch it.