A certain algorithm takes 10^-4 timesof 2^n seconds to solve an instance of size

Question

A certain algorithm takes 10^-4 timesof 2^n 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 timesof n^3 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.

Explanation / Answer

To solve an instance of size n , first algo. takes time = 10-4 x 2n seconds

=> 1 day = 3600 x 24 seconds, 1 year = 365x  3600 x 24 seconds = 3153.6 x 104 seconds

So, in 10-4 x 2n seconds first algo. solve an instance of size = n

=> in 1 second " " = n/ 10-4 x 2n = nx104/ 2n

Also, instance of size 1 is solve in 10-4 x 2 seconds.

So, it will solve the instance of size 38 in 38 x 2 x 10-4 = 76 x 10-3 seconds

On the machine of 100 times fast, instance solve in a year will be 38 * 4 = 152

For second algo. instance of size n is solved in n3 x 10-2 seconds.

So, in a year it will sove 297 instances.

Thus, we can find that the second machine is never slower than first.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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