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

Answer

in 10^-9 sec solves 1 instruction

therefore, in 1 sec solves 1/10^-9 = 10⁹ instruction

so, in 60*60 sec(i.e. 1 hr) solves 10⁹ * 60 * 60 instructions

Therefore, the largest problem size that can be solves in one hour by this processor if the number of steps needed to execute the algorithm is

n is (10⁹ * 60 * 60)/n

n² is (10⁹ * 60 * 60)/n²

n³ is (10⁹ * 60 * 60)/n³

log n is (10⁹ * 60 * 60)/ log n