Greedy Algorithm for license purchase problem

[Shaitan00]

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 rj > 1 each month, where rj is a given parameter. This means that if license j is purchased t months from now, it will cost 100×rtj . We will assume that all the price growth rates are distinct.

 

The question is: 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?

[Mr Skeptic]

Imagine how easy that problem would be if the licenses were sorted by rate of growth.

[Shaitan00]

How can it be easy to order exponential growth seeing as it depends on time (t).

 

For example - if you have 3^t and 4^(t/2+1) then it completly depends on (t), sometimes the first is smaller and other times the second is smaller, all depending on values of (t).

 

So how can you determine an order?

[Mr Skeptic]

This means that if license j is purchased t months from now, it will cost 100×rtj .

 

This is what confused me. I thought that you already had all of the licenses sorted by rate of growth. But I didn't notice that the example given here is not exponential growth. Is there a mistake in that equation? Is it supposed to be 100×r^(tj)? If so, you may benefit from rewriting it as 100×e^(t×j×ln r)