Question

If algorithm A and another algorithm B take log₂(n) and √n microseconds, respectively, to solve a problem, then the largest size n of a problem these algorithms can solve. respectively. in one second are_____ and _____.  
1. \({2^{{{10}^6}}}and\;{10^6}\)
2. \({2^{{{10}^6}}}and\;{10^{{12}}}\)
3. \({2^{{{10}^6}}}and\;{6.10^6}\)
4. \({2^{{{10}^6}}}and\;{6.10^{12}}\)

Answer 1

Correct Answer - Option 2 : \({2^{{{10}^6}}}and\;{10^{{12}}}\)

The correct answer is option 2.
Explanation:

A microsecond is 10^-6 seconds. Hence, one second =10⁶ microseconds

One hour=60x60x106= 3.6x10⁹ microseconds

One month=2.592x10¹²microseconds

One century=3.1104x1015microseconds

f(n)=logn in this case,the largest value n such that logn <=10⁶.

We rewrite as, 2^logn <= 2^{(10)^6} 

thus, 2^1000000 = (2¹⁰)¹⁰⁰⁰⁰⁰ = (10³)100000 = 10³⁰⁰⁰⁰⁰

Hence, log2(n) and √n, In one second

\({2^{{{10}^6}}}and\;{10^{{12}}}\) the value will be 10⁶ and 10⁶

Hence the correct answer is option 2.