• Support PF! Buy your school textbooks, materials and every day products Here!

Algorithm Time

  • Thread starter blackle
  • Start date
  • #1
8
0
• P1 takes n days to run
• 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!
 

Answers and Replies

  • #2
33,154
4,838
• P1 takes n days to run
• 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!
If I understand the problem correctly, if P1 runs for 12,000,000,000 years, n would not be 12,000,000,000 (which is in years); n would be 12,000,000,000 years x 365 days/year. This mistake affects all of your answers.

For the b part, if P1 takes n = 12,000,000,000 x 365 days, then on the faster computer P1 would take 12,000,000,000 x 365 /1,000,000 days, or 12,000 X 365 days. And so on for P2, P3, and P4.
 
  • #3
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,236
962
• P1 takes n days to run
• 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!
The problem statement is a bit confusing. For part (a), I take it to mean that:
Algorithm P1 takes n days to calculate n - or maybe n things.
Algorithm P2 takes n2 days to calculate n.
Algorithm P3 takes log2(n) days to calculate n.
Algorithm P4 takes 2n days to calculate n.​

There are on average, about 365.24 days per year, so there are approximately 365.24 (days/year)·12×109years ≈ 4.38×1012 days in 12 billion years.

It looks like you should compute each answer; in other words,
rather than saying that for P2: n = √(4.38×1012),
you should say that for P2: n = 2.09×106,
etc.​

For part (b):

This computer is 1 million times as fast, so Algorithm P1 takes n/1,000,000 days to calculate n - or maybe n things. Equivalently, Algorithm P1 takes n days to calculate n million. You could also think of this as follows: The fast computer can calculate in 12×109years what the slow computer (in part a) would require 12×1015 years to calculate.

The following may be handy for getting some of your results log2(x)=(1/ln(2))·ln(x) or log2(x)=(1/log10(2))·log10(x).

For instance, in part (a), P3 can calculate n = log2(4.38×1012) = (1/log10(2))·log10(4.38×1012) ≈ (3.3219)·[log10(4.38)+log10(1012)] = (3.3219)·[log10(4.38)+ 12]. Notice that log10(10k) = k

FYI: The Earth's sun has only about 5 billion years left - before burning out.
 
  • #4
8
0
Thanks everyone for the reply, especially Sammy :)
 
  • #5
33,154
4,838
Both SammyS and I were confused about what the problem was saying, especially this part: "calculate the value of n (rounded down) we could compute...". If this is the exact wording of the problem, you should probably get clarification on what it means from your instructor.

Computers don't generally compute a number; they perform an operation or a sequence of operations that results in a number.
 

Related Threads for: Algorithm Time

Replies
8
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
12
Views
878
Top