Please provide a detailed answer so that I may fully understand the problem and

Question

Please provide a detailed answer so that I may fully understand the problem and the solution. Thank you!

Two algorithms have running times of n2 and 10 nlog n microseconds respectively where the base of logarithms is 2. To implement the first algorithm it takes 4 hours of programmer time and 4 minutes of CPU time. The second algorithm can be implemented in 20 hours of programmer time and 15 minutes of CPU time. A programmer costs 25 dollars/hr and CPU time is 100 dollars/min. If it is decided to implement the second algorithm, how many times should this algorithm be run for n=1000 to justify its extra cost over the first algorithm?

Explanation / Answer

Total cost of implementing first algorithm = 4*25 + 4*100 = 500 dollars

Total cost of implementing second algorithm = 20*25 + 15*100 = 2000 dollars

Extra cost of implementing 2nd algorithm = (2000- 500) = 1500 dollars

Now, comimg to computational cost for n = 1000

=> Computational cost of executing first algorithm = n^2 = 1000^2 = 10^6

=> Computational cost of executing second algorithm = 10*n*log2(n) = (10*1000*log2(1000)) = 9.965*(10^4) = 10^5 (approx)

Therefore, let the number of times the second algorithm is to be executed is n in order to balance the cost of implementation i.e.

=> (10^5)*n = 10^6 + 1500 => 1000*n = 10015 => n = 10.015

Therefore, the 2nd algorithm must be executed atleast 11 times in order to cancel out the implementation cost.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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