Hmm, sorry this is approximate and not exact, but I know for the complete ranking you don't need more than O(N log N) since that's the lower (and upper) bound on comparison sortinghttp://en.wikipedia.org/wiki/Comparison_sort

<t>That's cool. That was suggested to me by my graduate algorithms teaching assistant, and he knows his stuff!For a slightly harder problem, try my other post "Drawing from a multi-nomial distribution...part II"I think Aaron and Peterw basically gave optimal answers to this question...thank you!! </t>

<t>Aaron, that's pretty interesting. That's one way to take advantage of special problem structure. Here's anotherIF you can approximate the probabilities with rational numbers, and there is some constant integer a, and "a" items fit in memory, then there are integers x1 ... xN so thatp(1) ~= x1 / a...

That's cool, I've never heard of that. Can you give a short description, or do I need to refer to a paper??

Anyone wanna take a shot at the "discretized" version: p(1) = x1 / a , p(2) = x2 / a, p(3) = x3 / a, ... and the parameter "a" fits in memoryO(1) is possible

Hint:Define L_(max) = MAX_i ( L_i )So L_(max) is the amount of machine time required by the job which needs the most machine timeDefine W_(avg) = (1/M) * SUM_i( L_i )W_(avg) = the total amount of machine-time required, divided by the number of machines

I was getting stuck for like 15 minutes before I realized...don't try to cover a square with 17 circles...that can't be done (or at least I don't know how to). Try with 25...

<t>[From an algorithms class with Gary Miller, does NOT require knowledge of algo)Your factory has M identical machines. There are N > M jobs to do. Each job must be scheduled to a single machine, cannot be split, and each job i requires L_i units of dedicated machine time . A machine can do only on...

<t>I am now taking a class at CMU MSCF taught by a Goldman Asset Management guy. He was a math professor at CMU for 9 years developing interior point algorithms and stuff...an insanely smart guy, and every bit as "quant" as anyone on this board I'm sure. He said (I'm HEAVILY paraphrasing) that there...

Got it...now I understand thanks

<t>Sure, you can wait until there have been N^2 updates, and your searches are still O( log(N^2)) = O(2 logN) = O(logN). It's so nice how logs work with asymptotics.I still think the regenerations would be O(1), however, I'm not familiar with asymptotic bounds below O(1) so I can't say for sureAnywa...

<t>Sorry, gambler B bets max every time??? it's not clear from the statementIf so, his probability to have any money at the end is 2^-100If he does win every bet, his wealth will be 50*3^100, since he triples his money each time. The product of these should give the expected value for gambler B. But...

<t>That's very clever...I didn't think of anything like that! It's sort of an O(1) update with a lag once in a whileI think, if all of the probability updates increase, rather than decrease, event probabilities, you can get guaranteed asymptotic average update time of O(1). All you do is wait until ...

<t>The first thing you said is what I meant...sorry. You needn't keep the sum of all the weights constant. In fact I'd suggest you don't, since otherwise any update would be O(N). Assume that we always keep track of the sum of the weights. Then, when we draw from the distribution, we draw a random u...

<t>You are given some multinomial distribution over N events. That is, you are given p(1), p(2), ..., p(N), where all of the p(i) are real and non-negative. The p(i) do NOT sum to 1...that is they are not normalized. There is a reason for this...of course you can normalize them yourself.The goal is ...