An algorithm is to be implemented and run on a processor tha

An algorithm is to be implemented and run on a processor that can execute a single instruction in an average of 10^9 seconds. What is the largest problem size that can be solved in one hour by the algorithm on this processor if the number of steps needed to execute the algorithm is n, n^2, n^3, log n? Assume n is the input size.

Solution

1 instruction can be executed in 10^-9 seconds. So in 1 second that processor will execute 10⁹ instructions.

So in 1 minute it will execute 60*10⁹ = 6*10^10.

So in 1 hour it will execute 60*6*10¹⁰ = 36*10^11.

And instruction size can vary a lot. A simple step like a = 1 will take 2 instruction in start and just increment it everytime to take one instruction from next time. So basicall 2 in start and rest it will be 1. Simmilarly you can take a statement in which you have lots of multiplication and divide or heavy manipulation. Something like this a*b + c*d+(e*f+4*5-2-3+4*5*a+(b / c)). This will take a lot of instruction in one step.

But as they are asking for maximum number you take the first one. That is 1 instruction on every step.

So for n step - it will solve problem of 36*10¹¹ size.

for n² - it will solve squareroot of 36*10¹¹ which is 1897366. So it will solve problem of that size input. You can use calculator to check it.

for n³ - it will solve cuberoot of 36*10¹¹ which is 15326. So it will solve problem with maximum input 15326.

For log n its tricky. If we take base as 2 then it can solve 2^{(3600000000000)} input size problem. How do I calculate just logn = 36*10¹¹ so n = 2^{3600000000000.}

If you have any doubt regarding that you can ask me.