Suppose that you can rent time on a supercomputer that does 1000000000 operation

Question

Suppose that you can rent time on a supercomputer that does 1000000000 operations per second, and that the rental is $3000/hr. Your company is willing to spend $17000 to solve the largest version of a certain problem it can.

a) If the best algorithm you know for solving this problem takes 5^n operations, where n is the size of the problem, what is the largest size you can solve?

b) Suppose that someone discovers an algorithm for the same problem that takes n^{5} operations. What size problem can you solve now?

Explanation / Answer

for $3000 it will have1000000000 operations

for $17000 it can solve 1000000000 * 17000/3000 = 5666666666.66 operations we can afford

now

a)

5^n < 5666666666.66

5^14 = 6103515625

so it should be less than 14

so the largest n size wwhich company can afford with this algorithm is 13.

b)

In this case n^5 < 5666666666.66

90^5 = 5904900000

so it should be less than 90.

So n = 89.

89 is the highest power which super computer can solve.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.