Suppose you are the algorithmatician of your company and the manager comes to you with the following problem. The company has to buy n different software products. Due to various constraints, the company can only buy at most one software product per month. Each software is currently selling for a price of $100. However, they become expensive each month according to the following formula: the cost of software j increases by a factor r;> 1 each month, where r; is a known parameter. This means that if software j is purchased t months from now, it will cost $100(r;). It is given that all price growth rates are distinct: that is, ri #r; for software i #j (even though at the start they all have the same price of $100). The question the manager poses for you is this: Given that the company can only buy at most one software product a month, in which order should it buy the products so that the total amount of money spent is as small as possible? In particular he has the following questions
a.Consider the following example to get started. Suppose rı = 2, r2 = 3, and r3 = 4. What is the best order to buy the three products and why? Give a greedy algorithm to find the optimal order assuming that we have n products to buy and the growth rate of product i is ri, 1