- #1

- 8

- 0

• P2 takes n^2 days to run

• P3 takes 2^n days to run

• P4 takes log(n) in base 2 days to run

So, to run P2 on an n of 4 would take 16 days.

a. For each version of the program, calculate the value of n (rounded down) we could compute if we let the program run for 12 billion years , which is (very) roughly how long until the Earth’s sun dies.

b. Let’s say we have access to a computer which runs one million times faster than the one above; so we could compute P1(1) in one millionth of a day. Write out the n we could compute for each of the above algorithms given this new processing power.

## The Attempt at a Solution

a) I believe I solved part a) correctly.

P1: n = 12 000 000 000

P2: n = SquareRoot(12 000 000 000)

P3: n = log(12 000 000 000) in base 2

P4: n = 2^12 000 000 000

b) I have been trying to grasp the problem. So what values are we exactly supposed to find?

I understand:

P1: n = 1 took 1 day. but processor is 1 million times faster so takes 1/1000000 days.

What I am confused about is what of P2 are we supposed to calculate?

P2: n = 1 took 1 day. - do we take n to be 1? or we calculate the value of n to run an algorithm for 1/1000000 days like we did in part a)?

Any help would be appreciated. Thanks!