Question

Problem 2.15. A certain algorithm takes 10-4 2n seconds to solve an instance of size n. Show that in a year it could just solve an instance of size 38. What size of instance could be solved in a year on a machine one hundred times as fast? A second algorithm takes 10-2 x n3 seconds to solve an instance of size n. What size instance can it solve in a year? What size instance could be solved in a year on a machine one hundred times as fast? Show that the second algorithm is nevertheless slower than the first for instances of size less than 20

Answer 1

In one year we have 365*24*60*60 seconds so we can find out the value of n which will take up this much of time so

which gives us

365 2460 60-104 2"

365 * 24 * 60 * 60 * 104 = 2n

taking log both sides gives us

n - log2(365 24 60 60104

or n =38.18 or n=38

For a machine that is 100 times fast it will take seconds which will make the calculation

10-б * 271

10-6 * 2n-365 * 24 * 60 * 60

Again taking log will give us

n - log2(365 24 60 106

or n=44.8 or n =44

PART 2

A similar approach as above gives us

n- (365 24 60 60 102)1/81466(approx)

For 100 times fast we get

n- (365 24 60 60 * 104)1/86806(approx)

part 3

We have to solve the inequality

10-2 * n3 > 10-4 * 2n

Hence we can see that on n=20

The inequality is

which is false

80104.8576

but for n=19 and less this holds i.e for n=19 we have

which is true

68.59 > 52.4

so the inequality reverses for n=20 and above

Do give a thumbs up and in case there are doubts leave a comment.