What is the size of an instance that can be solved with a gi

What is the size of an instance that can be solved with a given algorithm in ten minutes knowing that an instance of size 1,000,000 can be solved in 1 minute. Assume that the running time of the algorithm is An Choose the closest number from the answers below. 4.10 none of the listed more than 1010 but not more than 4 10 O I do not know 10 4.10 O 10

Solution

a) The answer is 10^7. Time taken for 10^6 is 1min, so for 10min the input should be 10^7.

b) The answer is 4,000. It is not listed. The run time is square root of n, The input should be 4000.