Question

An exponential algorithm requires 4^n (four to the power n) steps to solve a problem with an input of size n. Suppose it has been found that using today's computer, a direct implementation of that algorithm would be able to handle an input size of 30 in 10 years. If the computer is speeded up by a factor of 100 (with no other changes), what input size can be processed in the same time? Explain your answer.
(Hint: speeding up a computer by a certain factor means that the time taken per step is reduced by that factor. So, if today's computer takes time t per step, then the future 100-times speeded-up computer would take time t/100 per step.)

Answer 1

Given, time to solve 4³⁰ steps 10 years

Hence, time to solve 1 step 10/4³⁰ years

Now, time to solve 1 step with speeded-up computer 10/(4³⁰*100) years

Hence, now in 1 year, number of steps solved (4³⁰*100)/10;

Hence, in 10 years, number of steps solved 4³⁰*100

4³⁰*4^3.16

4³⁰⁺³ 4³³ steps

Hence, input size of n = 33 can be processed with speeded up computer in 10 years;