There are tyro algorithms called Alg1 and Alg2 fox a problem of size n. Alg1 run

Question

There are tyro algorithms called Alg1 and Alg2 fox a problem of size n. Alg1 runs in n2 microseconds and Alg2 runs in l00n log n microseconds. Alg1 can be implemented using 4 hours of programmer time and needs '2 minutes of CPL time. On the other hand. Alg2 requires 15 hours of programmer time and 6 minutes of CPU time. If programmers are paid 20 dollars per hour and CPL time costs 50 dollars per minute, how many times must a problem instance of size 500 be solved using Alg2 in order to justify its development cost?

Explanation / Answer

Algorithm 1: To run it once.

Fixed cost:4 hrs * $20/hr = $80

Runtime cost:

n^2 microsecond = (500)^2 microsecond = 250,000 microsecond = 250 second

we need to change seond in to minute to get runtime cost in min/hr

((250second * 1min)/(60second)) * $50/min = $208

Run the algorithm x times

C?(x)= 80 + (250/60)*50x

Algorithm 2: To run it once

Fixed cost: 15 hrs * $20/hr = $300

Runtime cost:

100n(logn) = 100*500*(log500) = 134948 microsecond = 135 second

We need to change second into minute to get runtime cost in min/hr

((135 second*1min)/(60 second)) * $50/min =$112.5

Run the algorithm x times

C?(x) = 300 + (135/ 60) * 50x

C?(x) = C?(x)

80 + 208X = 300 + 112X

208x

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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