Question

An exponential algorithm requires 4^n (four to the power n) steps to solve a problem with...

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.)

Given, time to solve 430 steps 10 years

Hence, time to solve 1 step 10/430 years

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

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

Hence, in 10 years, number of steps solved 430*100

430*43.16

430+3 433 steps

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

Earn Coins

Coins can be redeemed for fabulous gifts.