Your friends are starting a security company that needs to obtain licenses for n different pieces of cryptographic software. Due to regulations, they can only obtain these licenses at the rate of at most one per month.

Each license is currently selling for a price of $100. However, they are all becoming more expensive according to exponential growth curves: in particular, the cost of license j increases by a factor of r_j > 1 each month, where r_j is a given parameter. This means that if license j  is purchased t months from now, it will cost $100 r_j^t_.

We will assume that all the price growth rates are distinct; that is, r_i ≠ r_j for licenses i ≠ j (even though they start at the same price of  $100).

Given that the company can only buy at most one license a month, in which order should it buy the licenses so that the total amount of money it spends is as small as possible?

Provide the complexity of your algorithm

Which type of proof would you use for proving that your algorithm is optimal? State clearly what you need to prove, considering the type of proof you would use.