UGC NET CSE | October 2020 | Part 2 | Question: 25

Question

If algorithm $A$ and another algorithm $B$ take $\log_2 (n)$ and $\sqrt{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 ______.

• A. $2^{10^n}$ and $10^6$
• B. $2^{10^n}$ and $10^{12}$
• C. $2^{10^n}$ and $6.10^6$
• D. $2^{10^n}$ and $6.10^{12}$

Comments

it is 2^10^ 6 in actual question

Answer 1

 

For algorithm A problem solving time is log2(n) microseconds or lg(n) x 10-6 sec

 so in 1 sec what is the max value of n  such that lg n <= 10^6 

raising both side to power of n 

n<=2^10^6 

similarly 

for algorithm B  problem solving time is sqrt(n) microseconds or sqrt (n) x 10-6 sec

 so in 1 sec what is the max value of n  such that sqrt(n) <= 10^6 

squiring  both sides we get 

n<=10^6^2 =10^12 

Hence option B is correct ans 

https://udel.edu/~caviness/Class/CISC320-02S/exercise-solns/ch01/R-1.7.pdf