If algorithm A and another algorithm B take −− log (n) √n 2 and microseconds, respectively, to n solve a problem, then the largest size of a problem these algorithms can solve, respectively, in one second are ___ and _____

1. A2^(10⁶) and 10⁶
2. B2^(10⁶) and 10¹²
3. C2^(10⁶) and 6·10⁶
4. D2^(10⁶) and 6·10¹²

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. 2^(10⁶) and 10¹²

Explanation

One second is 10⁶ μs. log₂ n = 10⁶ gives n = 2^(10⁶); √n = 10⁶ gives n = 10¹².