Is BlackBerry a good investment?

Consider the following (unrealistic!) investment problem.We have a set S of n potential investments, each give?

• 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. Sent from my BlackBerry® wireless handheld from Glo Mobile

• Answer:

  This question is dumb. You sort the investments by return and then take all of the highest return investment, and continue taking the most of each investment in turn until you have exhausted your funds. The complexity of the investment is just the complexity of your sort algorithm which is likely not better than O(n log n).