1. A company needs to buy n set of gadgets GiG,Gneach costing co initially, but

Question

1. A company needs to buy n set of gadgets GiG,Gneach costing co initially, but their cost increase exponentially each month such that the cost of the component set i after k months is i-C0 , i-1, 2, , n. Note that > 1 are distinct, and and Coare known. Due to restrictions the company can only buy one component set cach month. (a) Propose a greedy algorithm for the order by which the component set must be purchased to minimize the total cost to the company. For example ifn-3, the order can be {Gj,G3.G2), iG2.Gj,G3), etc. and given values of rj,r2,r3, Co you must say which order minimizes that total cost. Note that your algorithm must be for the general case of n gadgets. The algorithm's complexity must be better than O(n) mpiar n (b) Prove that your algorithm provide the optimal solution, and determine its

Explanation / Answer

sort on the cost of gadgets (using quick or heap sort- Takes O(n * log n) time)

start from the end of the list and start coming back (Buying the most expensive time first)

This is the optimal alogrithm for buying the items because the question is basically a sorting algorithm and sorting cannot be done in better than O(nLog n) by help of heap or merge sort.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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