UN Blog: Consider the following (unrealistic!) investment problem.? and Save Darfur protest at Franklin Templeton Investments

Saturday, March 22, 2014

Consider the following (unrealistic!) investment problem.? and Save Darfur protest at Franklin Templeton Investments

Consider the following (unrealistic!) investment problem.?

Consider the following (unrealistic!) investment problem.

We have a set S of n potential investments, each given by a pair of floating point numbers (amount, estimated return) There is a total amount A to invest; we want to select investments to maximise the return on this amount.

One may select each investment (a,r) as a whole (spending all of a, and getting r return) or only can select only a fraction f (spending (f*a), and getting (f*r) return). The estimated return of a set of selections is the sum of the returns of the individual selections. Obviously, in selecting elements of S, we cannot spend more than the total amount A available.

Describe an efficient algorithm for computing the maximum estimated return that can be realised with amount A and set of investments S. What is the time complexity of your algorithm (in big-oh notation)?

Is it the best possible?

It is fine to describe your algorithm in words and/or pseudocode; there's no need to include code in a programming language.

Investment best answer:

Answer by James
Find each investment's return / amount ratio. Sort the investments by this amount (in descending order) in L

maximum return <- 0

While A is greater than 0 and the highest return / amount ratio is greater than 1
remove investment i from the front of L
fraction <- min(A, i.amount) / i.amount
maximum return <- maximum return + fraction * i.return
A <- A - fraction * i.amount
End While

return maximum return

time complexity:
sort: O(nlogn)
while loop: O(n)
total: O(nlogn) + O(n) = O(nlogn)

The time complexity is O(nlogn). I cannot imagine a better algorithm, so I'd say that it is the best possible, although I cannot guarantee it.

Edit: possibly remove the condition of "the highest return / amount ratio is greater than 1" from the while loop. In real life you'd want that, as it would make no sense to make an investment where the return is less than the amount, but the question seems to only want to maximise the return, and not maximise profit. So maybe investing $ 100 to make $ 10 is good, because the return is $ 10, as opposed to $ 0 for not investing the $ 100 (even though you'd have $ 100 unused capital), because all it's saying is maximise the return.
I assume you can assume all investments have a ratio greater than 1, as it would be silly to even consider other investments.